nmod_mat_init mat rows cols n

Initialises mat to a rows-by-cols matrix with coefficients modulo \(n\), where \(n\) can be any nonzero integer that fits in a limb. All elements are set to zero.

nmod_mat_init_set mat src

Initialises mat and sets its dimensions, modulus and elements to those of src.

nmod_mat_clear mat

Clears the matrix and releases any memory it used. The matrix cannot be used again until it is initialised. This function must be called exactly once when finished using an nmod_mat_t object.

nmod_mat_set mat src

Sets mat to a copy of src. It is assumed that mat and src have identical dimensions.

nmod_mat_swap mat1 mat2

Exchanges mat1 and mat2.

nmod_mat_swap_entrywise mat1 mat2

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

nmod_mat_get_entry mat i j

Get the entry at row \(i\) and column \(j\) of the matrix mat.

nmod_mat_entry_ptr mat i j

Return a pointer to the entry at row \(i\) and column \(j\) of the matrix mat.

nmod_mat_set_entry mat i j x

Set the entry at row \(i\) and column \(j\) of the matrix mat to x.

nmod_mat_nrows mat

Returns the number of rows in mat.

nmod_mat_ncols mat

Returns the number of columns in mat.

nmod_mat_zero mat

Sets all entries of the matrix mat to zero.

nmod_mat_is_zero mat

Returns \(1\) if all entries of the matrix mat are zero.

nmod_mat_window_init window mat r1 c1 r2 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.

nmod_mat_window_clear 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.

nmod_mat_concat_vertical res mat1 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\).

nmod_mat_concat_horizontal res mat1 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)\).

nmod_mat_print_pretty mat

Pretty-prints mat to stdout. A header is printed followed by the rows enclosed in brackets. Each column is right-aligned to the width of the modulus written in decimal, and the columns are separated by spaces. For example:

<2 x 3 integer matrix mod 2903>
[   0    0 2607]
[ 622    0    0]

nmod_mat_randtest mat state

Sets the elements to a random matrix with entries between \(0\) and \(m-1\) inclusive, where \(m\) is the modulus of mat. A sparse matrix is generated with increased probability.

nmod_mat_randfull mat state

Sets the element to random numbers likely to be close to the modulus of the matrix. This is used to test potential overflow-related bugs.

nmod_mat_randpermdiag mat state diag n

Sets mat to a random permutation of the diagonal matrix with \(n\) leading entries given by the vector diag. It is assumed that the main diagonal of mat has room for at least \(n\) entries.

Returns \(0\) or \(1\), depending on whether the permutation is even or odd respectively.

nmod_mat_randrank mat state rank

Sets mat to a random sparse matrix with the given rank, having exactly as many non-zero elements as the rank, with the non-zero elements being uniformly random integers between \(0\) and \(m-1\) inclusive, where \(m\) is the modulus of mat.

The matrix can be transformed into a dense matrix with unchanged rank by subsequently calling nmod_mat_randops.

nmod_mat_randops mat count state

Randomises mat by performing elementary row or column operations. More precisely, at most count random additions or subtractions of distinct rows and columns will be performed. This leaves the rank (and for square matrices, determinant) unchanged.

nmod_mat_randtril mat state unit

Sets mat to a random lower triangular matrix. If unit is 1, it will have ones on the main diagonal, otherwise it will have random nonzero entries on the main diagonal.

nmod_mat_randtriu mat state unit

Sets mat to a random upper triangular matrix. If unit is 1, it will have ones on the main diagonal, otherwise it will have random nonzero entries on the main diagonal.

nmod_mat_equal mat1 mat2

Returns nonzero if mat1 and mat2 have the same dimensions and elements, and zero otherwise. The moduli are ignored.

nmod_mat_is_zero_row mat i

Returns a non-zero value if row \(i\) of mat is zero.

nmod_mat_transpose B A

Sets \(B\) to the transpose of \(A\). Dimensions must be compatible. \(B\) and \(A\) may be the same object if and only if the matrix is square.

nmod_mat_swap_rows mat perm r s

Swaps rows r and s of mat. If perm is non-NULL, the permutation of the rows will also be applied to perm.

nmod_mat_swap_cols mat perm r s

Swaps columns r and s of mat. If perm is non-NULL, the permutation of the columns will also be applied to perm.

nmod_mat_invert_rows mat perm

Swaps rows i and r - i of mat for 0 <= i < r/2, where r is the number of rows of mat. If perm is non-NULL, the permutation of the rows will also be applied to perm.

nmod_mat_invert_cols mat perm

Swaps columns i and c - i of mat for 0 <= i < c/2, where c is the number of columns of mat. If perm is non-NULL, the permutation of the columns will also be applied to perm.

nmod_mat_permute_rows mat perm_act perm_store

Permutes rows of the matrix mat according to permutation perm_act and, if perm_store is not NULL, apply the same permutation to it.

nmod_mat_add C A B

Computes \(C = A + B\). Dimensions must be identical.

nmod_mat_sub C A B

Computes \(C = A - B\). Dimensions must be identical.

nmod_mat_neg A B

Sets \(B = -A\). Dimensions must be identical.

nmod_mat_scalar_mul B A c

Sets \(B = cA\), where the scalar \(c\) is assumed to be reduced modulo the modulus. Dimensions of \(A\) and \(B\) must be identical.

nmod_mat_scalar_addmul_ui dest X Y b

Sets \(dest = X + bY\), where the scalar \(b\) is assumed to be reduced modulo the modulus. Dimensions of dest, X and Y must be identical. dest can be aliased with X or Y.

nmod_mat_scalar_mul_fmpz res M c

Sets \(B = cA\), where the scalar \(c\) is of type fmpz_t. Dimensions of \(A\) and \(B\) must be identical.

nmod_mat_mul C A B

Sets \(C = AB\). Dimensions must be compatible for matrix multiplication. Aliasing is allowed. This function automatically chooses between classical and Strassen multiplication.

_nmod_mat_mul_classical_op D C A B op

Sets D = A*B op C where op is +1 for addition, -1 for subtraction and 0 to ignore C.

nmod_mat_mul_classical C A B

Sets \(C = AB\). Dimensions must be compatible for matrix multiplication. \(C\) is not allowed to be aliased with \(A\) or \(B\). Uses classical matrix multiplication, creating a temporary transposed copy of \(B\) to improve memory locality if the matrices are large enough, and packing several entries of \(B\) into each word if the modulus is very small.

_nmod_mat_mul_classical_threaded_pool_op D C A B op threads num_threads

Multithreaded version of _nmod_mat_mul_classical.

_nmod_mat_mul_classical_threaded_op D C A B op

Multithreaded version of _nmod_mat_mul_classical.

nmod_mat_mul_classical_threaded C A B

Multithreaded version of nmod_mat_mul_classical.

nmod_mat_mul_strassen C A B

Sets \(C = AB\). Dimensions must be compatible for matrix multiplication. \(C\) is not allowed to be aliased with \(A\) or \(B\). Uses Strassen multiplication (the Strassen-Winograd variant).

nmod_mat_mul_blas C A B

Tries to set \(C = AB\) using BLAS and returns \(1\) for success and \(0\) for failure. Dimensions must be compatible for matrix multiplication.

nmod_mat_addmul D C A B

Sets \(D = C + AB\). \(C\) and \(D\) may be aliased with each other but not with \(A\) or \(B\). Automatically selects between classical and Strassen multiplication.

nmod_mat_submul D C A B

Sets \(D = C + AB\). \(C\) and \(D\) may be aliased with each other but not with \(A\) or \(B\).

nmod_mat_mul_nmod_vec c A b 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.

nmod_mat_nmod_vec_mul c a alen 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.

_nmod_mat_pow dest mat pow

Sets \(dest = mat^{pow}\). dest and mat cannot be aliased. Implements exponentiation by squaring.

nmod_mat_pow dest mat pow

Sets \(dest = mat^{pow}\). dest and mat may be aliased. Implements exponentiation by squaring.

nmod_mat_trace mat

Computes the trace of the matrix, i.e. the sum of the entries on the main diagonal. The matrix is required to be square.

nmod_mat_det_howell A

Returns the determinant of \(A\).

nmod_mat_det A

Returns the determinant of \(A\).

nmod_mat_rank A

Returns the rank of \(A\). The modulus of \(A\) must be a prime number.

nmod_mat_inv B A

Sets \(B = A^{-1}\) and returns \(1\) if \(A\) is invertible. If \(A\) is singular, returns \(0\) and sets the elements of \(B\) to undefined values.

\(A\) and \(B\) must be square matrices with the same dimensions and modulus. The modulus must be prime.

nmod_mat_solve_tril X L B unit

Sets \(X = L^{-1} B\) where \(L\) is a full rank lower triangular square matrix. If unit = 1, \(L\) is assumed to have ones on its main diagonal, and the main diagonal will not be read. \(X\) and \(B\) are allowed to be the same matrix, but no other aliasing is allowed. Automatically chooses between the classical and recursive algorithms.

nmod_mat_solve_tril_classical X L B unit

Sets \(X = L^{-1} B\) where \(L\) is a full rank lower triangular square matrix. If unit = 1, \(L\) is assumed to have ones on its main diagonal, and the main diagonal will not be read. \(X\) and \(B\) are allowed to be the same matrix, but no other aliasing is allowed. Uses forward substitution.

nmod_mat_solve_tril_recursive X L B unit

Sets \(X = L^{-1} B\) where \(L\) is a full rank lower triangular square matrix. If unit = 1, \(L\) is assumed to have ones on its main diagonal, and the main diagonal will not be read. \(X\) and \(B\) are allowed to be the same matrix, but no other aliasing is allowed.

Uses the block inversion formula

\[\begin{aligned} ` \begin{pmatrix} A & 0 \\ C & D \end{pmatrix}^{-1} \begin{pmatrix} X \\ Y \end{pmatrix} = \begin{pmatrix} A^{-1} X \\ D^{-1} ( Y - C A^{-1} X ) \end{pmatrix} \end{aligned}\]

to reduce the problem to matrix multiplication and triangular solving of smaller systems.

nmod_mat_solve_triu X U B unit

Sets \(X = U^{-1} B\) where \(U\) is a full rank upper triangular square matrix. If unit = 1, \(U\) is assumed to have ones on its main diagonal, and the main diagonal will not be read. \(X\) and \(B\) are allowed to be the same matrix, but no other aliasing is allowed. Automatically chooses between the classical and recursive algorithms.

nmod_mat_solve_triu_classical X U B unit

Sets \(X = U^{-1} B\) where \(U\) is a full rank upper triangular square matrix. If unit = 1, \(U\) is assumed to have ones on its main diagonal, and the main diagonal will not be read. \(X\) and \(B\) are allowed to be the same matrix, but no other aliasing is allowed. Uses forward substitution.

nmod_mat_solve_triu_recursive X U B unit

Sets \(X = U^{-1} B\) where \(U\) is a full rank upper triangular square matrix. If unit = 1, \(U\) is assumed to have ones on its main diagonal, and the main diagonal will not be read. \(X\) and \(B\) are allowed to be the same matrix, but no other aliasing is allowed.

Uses the block inversion formula

\[\begin{aligned} ` \begin{pmatrix} A & B \\ 0 & D \end{pmatrix}^{-1} \begin{pmatrix} X \\ Y \end{pmatrix} = \begin{pmatrix} A^{-1} (X - B D^{-1} Y) \\ D^{-1} Y \end{pmatrix} \end{aligned}\]

to reduce the problem to matrix multiplication and triangular solving of smaller systems.

nmod_mat_solve X A B

Solves the matrix-matrix equation \(AX = B\) over \(\mathbb{Z} / p \mathbb{Z}\) where \(p\) is the modulus of \(X\) which must be a prime number. \(X\), \(A\), and \(B\) should have the same moduli.

Returns \(1\) if \(A\) has full rank; otherwise returns \(0\) and sets the elements of \(X\) to undefined values.

The matrix \(A\) must be square.

nmod_mat_can_solve_inner rank perm pivots X A B

As for nmod_mat_can_solve except that if \(rank\) is not \(NULL\) the value it points to will be set to the rank of \(A\). If \(perm\) is not \(NULL\) then it must be a valid initialised permutation whose length is the number of rows of \(A\). After the function call it will be set to the row permutation given by LU decomposition of \(A\). If \(pivots\) is not \(NULL\) then it must an initialised vector. Only the first \(*rank\) of these will be set by the function call. They are set to the columns of the pivots chosen by the LU decomposition of \(A\).

nmod_mat_can_solve X A B

Solves the matrix-matrix equation \(AX = B\) over \(\mathbb{Z} / p \mathbb{Z}\) where \(p\) is the modulus of \(X\) which must be a prime number. \(X\), \(A\), and \(B\) should have the same moduli.

Returns \(1\) if a solution exists; otherwise returns \(0\) and sets the elements of \(X\) to zero. If more than one solution exists, one of the valid solutions is given.

There are no restrictions on the shape of \(A\) and it may be singular.

nmod_mat_solve_vec x A b

Solves the matrix-vector equation \(Ax = b\) over \(\mathbb{Z} / p \mathbb{Z}\) where \(p\) is the modulus of \(A\) which must be a prime number.

Returns \(1\) if \(A\) has full rank; otherwise returns \(0\) and sets the elements of \(x\) to undefined values.

nmod_mat_lu P A rank_check

Computes a generalised LU decomposition \(LU = PA\) of a given matrix \(A\), returning the rank of \(A\).

If \(A\) is a nonsingular square matrix, it will be overwritten with a unit diagonal lower triangular matrix \(L\) and an upper triangular matrix \(U\) (the diagonal of \(L\) will not be stored explicitly).

If \(A\) is an arbitrary matrix of rank \(r\), \(U\) will be in row echelon form having \(r\) nonzero rows, and \(L\) will be lower triangular but truncated to \(r\) columns, having implicit ones on the \(r\) first entries of the main diagonal. All other entries will be zero.

If a nonzero value for rank_check is passed, the function will abandon the output matrix in an undefined state and return 0 if \(A\) is detected to be rank-deficient.

The classical version uses direct Gaussian elimination. The classical_delayed version also uses Gaussian elimination, but performs delayed modular reductions. The recursive version uses block recursive decomposition. The default function chooses an algorithm automatically.

nmod_mat_rref A

Puts \(A\) in reduced row echelon form and returns the rank of \(A\).

The rref is computed by first obtaining an unreduced row echelon form via LU decomposition and then solving an additional triangular system.

nmod_mat_reduce_row A P L n

Reduce row n of the matrix \(A\), assuming the prior rows are in Gauss form. However those rows may not be in order. The entry \(i\) of the array \(P\) is the row of \(A\) which has a pivot in the \(i\)-th column. If no such row exists, the entry of \(P\) will be \(-1\). The function returns the column in which the \(n\)-th row has a pivot after reduction. This will always be chosen to be the first available column for a pivot from the left. This information is also updated in \(P\). Entry \(i\) of the array \(L\) contains the number of possibly nonzero columns of \(A\) row \(i\). This speeds up reduction in the case that \(A\) is chambered on the right. Otherwise the entries of \(L\) can all be set to the number of columns of \(A\). We require the entries of \(L\) to be monotonic increasing.

nmod_mat_nullspace X A

Computes the nullspace of \(A\) and returns the nullity.

More precisely, this function sets \(X\) to a maximum rank matrix such that \(AX = 0\) and returns the rank of \(X\). The columns of \(X\) will form a basis for the nullspace of \(A\).

\(X\) must have sufficient space to store all basis vectors in the nullspace.

This function computes the reduced row echelon form and then reads off the basis vectors.

nmod_mat_similarity M r d

Applies a similarity transform to the \(n\times n\) matrix \(M\) in-place.

If \(P\) is the \(n\times n\) identity matrix the zero entries of whose row \(r\) (0-indexed) have been replaced by \(d\), this transform is equivalent to \(M = P^{-1}MP\).

Similarity transforms preserve the determinant, characteristic polynomial and minimal polynomial.

The value \(d\) is required to be reduced modulo the modulus of the entries in the matrix.

nmod_mat_charpoly_berkowitz p M

Compute the characteristic polynomial \(p\) of the matrix \(M\). The matrix is required to be square, otherwise an exception is raised. The danilevsky algorithm assumes that the modulus is prime.

nmod_mat_minpoly p M

Compute the minimal polynomial \(p\) of the matrix \(M\). The matrix is required to be square, otherwise an exception is raised.

nmod_mat_strong_echelon_form A

Puts \(A\) into strong echelon form. 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. Note that [FieHof2014] defines strong echelon form as a lower left normal form, while the implemented version returns an upper right normal form, agreeing with the definition of Howell form in [StoMul1998].

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

nmod_mat_howell_form A

Puts \(A\) into Howell form and returns the number of non-zero rows. For a definition of the Howell form see [StoMul1998]. The Howell form is computed by first putting \(A\) into strong echelon form and then ordering the rows.

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