fmpz_mod_mat.h – matrices over integers mod n

Description.

Types, macros and constants

type fmpz_mod_mat_struct
type fmpz_mod_mat_t

Description.

type fmpz_mod_mat_struct
type fmpz_mod_mat_t

Description.

Element access

fmpz *fmpz_mod_mat_entry(const fmpz_mod_mat_t mat, slong i, slong j)

Return a reference to the element at row i and column j of mat.

void fmpz_mod_mat_set_entry(fmpz_mod_mat_t mat, slong i, slong j, const fmpz_t val)

Set the entry at row i and column j of mat to val.

Memory management

void fmpz_mod_mat_init(fmpz_mod_mat_t mat, slong rows, slong cols, const fmpz_t n)

Initialise mat as a matrix with the given number of rows and cols and modulus n.

void fmpz_mod_mat_init_set(fmpz_mod_mat_t mat, const fmpz_mod_mat_t src)

Initialise mat and set it equal to the matrix src, including the number of rows and columns and the modulus.

void fmpz_mod_mat_clear(fmpz_mod_mat_t mat)

Clear mat and release any memory it used.

Basic manipulation ——————————————————————————–

slong fmpz_mod_mat_nrows(const fmpz_mod_mat_t mat)

Return the number of rows of mat.

slong fmpz_mod_mat_ncols(const fmpz_mod_mat_t mat)

Return the number of columns of mat.

void _fmpz_mod_mat_set_mod(fmpz_mod_mat_t mat, const fmpz_t n)

Set the modulus of the matrix mat to n.

void fmpz_mod_mat_one(fmpz_mod_mat_t mat)

Set mat to the identity matrix (ones down the diagonal).

void fmpz_mod_mat_zero(fmpz_mod_mat_t mat)

Set mat to the zero matrix.

void fmpz_mod_mat_swap(fmpz_mod_mat_t mat1, fmpz_mod_mat_t mat2)

Efficiently swap the matrices mat1 and mat2.

void fmpz_mod_mat_swap_entrywise(fmpz_mod_mat_t mat1, fmpz_mod_mat_t mat2)

Swaps two matrices by swapping the individual entries rather than swapping the contents of the structs.

int fmpz_mod_mat_is_empty(const fmpz_mod_mat_t mat)

Return \(1\) if mat has either zero rows or columns.

int fmpz_mod_mat_is_square(const fmpz_mod_mat_t mat)

Return \(1\) if mat has the same number of rows and columns.

void _fmpz_mod_mat_reduce(fmpz_mod_mat_t mat)

Reduce all the entries of mat by the modulus n. This function is only needed internally.

Random generation

void fmpz_mod_mat_randtest(fmpz_mod_mat_t mat, flint_rand_t state)

Generate a random matrix with the existing dimensions and entries in \([0, n)\) where n is the modulus.

Windows and concatenation

void fmpz_mod_mat_window_init(fmpz_mod_mat_t window, const fmpz_mod_mat_t mat, slong r1, slong c1, slong r2, slong c2)

Initializes the matrix window to be an r2 - r1 by c2 - c1 submatrix of mat whose (0, 0) entry is the (r1, c1) entry of mat. The memory for the elements of window is shared with mat.

void fmpz_mod_mat_window_clear(fmpz_mod_mat_t window)

Clears the matrix window and releases any memory that it uses. Note that the memory to the underlying matrix that window points to is not freed.

void fmpz_mod_mat_concat_horizontal(fmpz_mod_mat_t res, const fmpz_mod_mat_t mat1, const fmpz_mod_mat_t mat2)

Sets res to vertical concatenation of (mat1, mat2) in that order. Matrix dimensions : mat1 : \(m \times n\), mat2 : \(k \times n\), res : \((m + k) \times n\).

void fmpz_mod_mat_concat_vertical(fmpz_mod_mat_t res, const fmpz_mod_mat_t mat1, const fmpz_mod_mat_t mat2)

Sets res to horizontal concatenation of (mat1, mat2) in that order. Matrix dimensions : mat1 : \(m \times n\), mat2 : \(m \times k\), res : \(m \times (n + k)\).

Input and output

void fmpz_mod_mat_print_pretty(const fmpz_mod_mat_t mat)

Prints the given matrix to stdout. The format is an opening square bracket then on each line a row of the matrix, followed by a closing square bracket. Each row is written as an opening square bracket followed by a space separated list of coefficients followed by a closing square bracket.

Comparison

int fmpz_mod_mat_is_zero(const fmpz_mod_mat_t mat)

Return \(1\) if mat is the zero matrix.

Set and transpose

void fmpz_mod_mat_set(fmpz_mod_mat_t B, const fmpz_mod_mat_t A)

Set B to equal A.

void fmpz_mod_mat_transpose(fmpz_mod_mat_t B, const fmpz_mod_mat_t A)

Set B to the transpose of A.

Conversions

void fmpz_mod_mat_set_fmpz_mat(fmpz_mod_mat_t A, const fmpz_mat_t B)

Set A to the matrix B reducing modulo the modulus of A.

void fmpz_mod_mat_get_fmpz_mat(fmpz_mat_t A, const fmpz_mod_mat_t B)

Set A to a lift of B.

Addition and subtraction

void fmpz_mod_mat_add(fmpz_mod_mat_t C, const fmpz_mod_mat_t A, const fmpz_mod_mat_t B)

Set C to \(A + B\).

void fmpz_mod_mat_sub(fmpz_mod_mat_t C, const fmpz_mod_mat_t A, const fmpz_mod_mat_t B)

Set C to \(A - B\).

void fmpz_mod_mat_neg(fmpz_mod_mat_t B, const fmpz_mod_mat_t A)

Set B to \(-A\).

Scalar arithmetic

void fmpz_mod_mat_scalar_mul_si(fmpz_mod_mat_t B, const fmpz_mod_mat_t A, slong c)

Set B to \(cA\) where c is a constant.

void fmpz_mod_mat_scalar_mul_ui(fmpz_mod_mat_t B, const fmpz_mod_mat_t A, slong c)

Set B to \(cA\) where c is a constant.

void fmpz_mod_mat_scalar_mul_fmpz(fmpz_mod_mat_t B, const fmpz_mod_mat_t A, fmpz_t c)

Set B to \(cA\) where c is a constant.

Matrix multiplication

void fmpz_mod_mat_mul(fmpz_mod_mat_t C, const fmpz_mod_mat_t A, const fmpz_mod_mat_t B)

Set C to A\times B. The number of rows of B must match the number of columns of A.

void _fmpz_mod_mat_mul_classical_threaded_pool_op(fmpz_mod_mat_t D, const fmpz_mod_mat_t C, const fmpz_mod_mat_t A, const fmpz_mod_mat_t B, int op, thread_pool_handle *threads, slong num_threads)

Set D to A\times B + op*C where op is +1, -1 or 0.

void _fmpz_mod_mat_mul_classical_threaded_op(fmpz_mod_mat_t D, const fmpz_mod_mat_t C, const fmpz_mod_mat_t A, const fmpz_mod_mat_t B, int op)

Set D to A\times B + op*C where op is +1, -1 or 0.

void fmpz_mod_mat_mul_classical_threaded(fmpz_mod_mat_t C, const fmpz_mod_mat_t A, const fmpz_mod_mat_t B)

Set C to A\times B. The number of rows of B must match the number of columns of A.

void fmpz_mod_mat_sqr(fmpz_mod_mat_t B, const fmpz_mod_mat_t A)

Set B to A^2. The matrix A must be square.

void fmpz_mod_mat_mul_fmpz_vec(fmpz *c, const fmpz_mod_mat_t A, const fmpz *b, slong blen)
void fmpz_mod_mat_mul_fmpz_vec_ptr(fmpz *const *c, const fmpz_mod_mat_t A, const fmpz *const *b, slong blen)

Compute a matrix-vector product of A and (b, blen) and store the result in c. The vector (b, blen) is either truncated or zero-extended to the number of columns of A. The number entries written to c is always equal to the number of rows of A.

void fmpz_mod_mat_fmpz_vec_mul(fmpz *c, const fmpz *a, slong alen, const fmpz_mod_mat_t B)
void fmpz_mod_mat_fmpz_vec_mul_ptr(fmpz *const *c, const fmpz *const *a, slong alen, const fmpz_mod_mat_t B)

Compute a vector-matrix product of (a, alen) and B and and store the result in c. The vector (a, alen) is either truncated or zero-extended to the number of rows of B. The number entries written to c is always equal to the number of columns of B.

Trace

void fmpz_mod_mat_trace(fmpz_t trace, const fmpz_mod_mat_t mat)

Set trace to the trace of the matrix mat.

Gaussian elimination

slong fmpz_mod_mat_rref(slong *perm, fmpz_mod_mat_t mat)

Uses Gauss-Jordan elimination to set mat to its reduced row echelon form and returns the rank of mat.

If perm is non-NULL, the permutation of rows in the matrix will also be applied to perm.

Strong echelon form and Howell form

void fmpz_mod_mat_strong_echelon_form(fmpz_mod_mat_t mat)

Transforms \(mat\) into the strong echelon form of \(mat\). The Howell form and the strong echelon form are equal up to permutation of the rows, see [FieHof2014] for a definition of the strong echelon form and the algorithm used here.

\(mat\) must have at least as many rows as columns.

slong fmpz_mod_mat_howell_form(fmpz_mod_mat_t mat)

Transforms \(mat\) into the Howell form of \(mat\). For a definition of the Howell form see [StoMul1998]. The Howell form is computed by first putting \(mat\) into strong echelon form and then ordering the rows.

\(mat\) must have at least as many rows as columns.