nmod_poly_mat_init mat rows cols n

Initialises a matrix with the given number of rows and columns for use. The modulus is set to \(n\).

nmod_poly_mat_init_set mat src

Initialises a matrix mat of the same dimensions and modulus as src, and sets it to a copy of src.

nmod_poly_mat_clear mat

Frees all memory associated with the matrix. The matrix must be reinitialised if it is to be used again.

nmod_poly_mat_nrows mat

Returns the number of rows in mat.

nmod_poly_mat_ncols mat

Returns the number of columns in mat.

nmod_poly_mat_modulus mat

Returns the modulus of mat.

nmod_poly_mat_entry mat i j

Gives a reference to the entry at row i and column j. The reference can be passed as an input or output variable to any nmod_poly function for direct manipulation of the matrix element. No bounds checking is performed.

nmod_poly_mat_set mat1 mat2

Sets mat1 to a copy of mat2.

nmod_poly_mat_swap mat1 mat2

Swaps mat1 and mat2 efficiently.

nmod_poly_mat_swap_entrywise mat1 mat2

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

nmod_poly_mat_print mat x

Prints the matrix mat to standard output, using the variable x.

nmod_poly_mat_randtest mat state len

This is equivalent to applying nmod_poly_randtest to all entries in the matrix.

nmod_poly_mat_randtest_sparse A state len density

Creates a random matrix with the amount of nonzero entries given approximately by the density variable, which should be a fraction between 0 (most sparse) and 1 (most dense).

The nonzero entries will have random lengths between 1 and len.

nmod_poly_mat_zero mat

Sets mat to the zero matrix.

nmod_poly_mat_one mat

Sets mat to the unit or identity matrix of given shape, having the element 1 on the main diagonal and zeros elsewhere. If mat is nonsquare, it is set to the truncation of a unit matrix.

nmod_poly_mat_equal mat1 mat2

Returns nonzero if mat1 and mat2 have the same shape and all their entries agree, and returns zero otherwise.

nmod_poly_mat_is_zero mat

Returns nonzero if all entries in mat are zero, and returns zero otherwise.

nmod_poly_mat_is_one mat

Returns nonzero if all entry of mat on the main diagonal are the constant polynomial 1 and all remaining entries are zero, and returns zero otherwise. The matrix need not be square.

nmod_poly_mat_is_empty mat

Returns a non-zero value if the number of rows or the number of columns in mat is zero, and otherwise returns zero.

nmod_poly_mat_is_square mat

Returns a non-zero value if the number of rows is equal to the number of columns in mat, and otherwise returns zero.

nmod_poly_mat_max_length A

Returns the maximum polynomial length among all the entries in A.

nmod_poly_mat_evaluate_nmod B A x

Sets the nmod_mat_t B to A evaluated entrywise at the point x.

nmod_poly_mat_scalar_mul_nmod_poly B A c

Sets B to A multiplied entrywise by the polynomial c.

nmod_poly_mat_scalar_mul_nmod B A c

Sets B to A multiplied entrywise by the coefficient c, which is assumed to be reduced modulo the modulus.

nmod_poly_mat_add C A B

Sets C to the sum of A and B. All matrices must have the same shape. Aliasing is allowed.

nmod_poly_mat_sub C A B

Sets C to the sum of A and B. All matrices must have the same shape. Aliasing is allowed.

nmod_poly_mat_neg B A

Sets B to the negation of A. The matrices must have the same shape. Aliasing is allowed.

nmod_poly_mat_mul C A B

Sets C to the matrix product of A and B. The matrices must have compatible dimensions for matrix multiplication. Aliasing is allowed. This function automatically chooses between classical, KS and evaluation-interpolation multiplication.

nmod_poly_mat_mul_classical C A B

Sets C to the matrix product of A and B, computed using the classical algorithm. The matrices must have compatible dimensions for matrix multiplication. Aliasing is allowed.

nmod_poly_mat_mul_KS C A B

Sets C to the matrix product of A and B, computed using Kronecker segmentation. The matrices must have compatible dimensions for matrix multiplication. Aliasing is allowed.

nmod_poly_mat_mul_interpolate C A B

Sets C to the matrix product of A and B, computed through evaluation and interpolation. The matrices must have compatible dimensions for matrix multiplication. For interpolation to be well-defined, we require that the modulus is a prime at least as large as \(m + n - 1\) where \(m\) and \(n\) are the maximum lengths of polynomials in the input matrices. Aliasing is allowed.

nmod_poly_mat_sqr B A

Sets B to the square of A, which must be a square matrix. Aliasing is allowed. This function automatically chooses between classical and KS squaring.

nmod_poly_mat_sqr_classical B A

Sets B to the square of A, which must be a square matrix. Aliasing is allowed. This function uses direct formulas for very small matrices, and otherwise classical matrix multiplication.

nmod_poly_mat_sqr_KS B A

Sets B to the square of A, which must be a square matrix. Aliasing is allowed. This function uses Kronecker segmentation.

nmod_poly_mat_sqr_interpolate B A

Sets B to the square of A, which must be a square matrix, computed through evaluation and interpolation. For interpolation to be well-defined, we require that the modulus is a prime at least as large as \(2n - 1\) where \(n\) is the maximum length of polynomials in the input matrix. Aliasing is allowed.

nmod_poly_mat_pow B A exp

Sets B to A raised to the power exp, where A is a square matrix. Uses exponentiation by squaring. Aliasing is allowed.

nmod_poly_mat_find_pivot_any mat start_row end_row c

Attempts to find a pivot entry for row reduction. Returns a row index \(r\) between start_row (inclusive) and stop_row (exclusive) such that column \(c\) in mat has a nonzero entry on row \(r\), or returns -1 if no such entry exists.

This implementation simply chooses the first nonzero entry from it encounters. This is likely to be a nearly optimal choice if all entries in the matrix have roughly the same size, but can lead to unnecessary coefficient growth if the entries vary in size.

nmod_poly_mat_find_pivot_partial mat start_row end_row c

Attempts to find a pivot entry for row reduction. Returns a row index \(r\) between start_row (inclusive) and stop_row (exclusive) such that column \(c\) in mat has a nonzero entry on row \(r\), or returns -1 if no such entry exists.

This implementation searches all the rows in the column and chooses the nonzero entry of smallest degree. This heuristic typically reduces coefficient growth when the matrix entries vary in size.

nmod_poly_mat_fflu B den perm A rank_check

Uses fraction-free Gaussian elimination to set (B, den) to a fraction-free LU decomposition of A and returns the rank of A. Aliasing of A and B is allowed.

Pivot elements are chosen with nmod_poly_mat_find_pivot_partial. If perm is non-NULL, the permutation of rows in the matrix will also be applied to perm.

If rank_check is set, the function aborts and returns 0 if the matrix is detected not to have full rank without completing the elimination.

The denominator den is set to \(\pm \operatorname{det}(A)\), where the sign is decided by the parity of the permutation. Note that the determinant is not generally the minimal denominator.

nmod_poly_mat_rref B den A

Sets (B, den) to the reduced row echelon form of A and returns the rank of A. Aliasing of A and B is allowed.

The denominator den is set to \(\pm \operatorname{det}(A)\). Note that the determinant is not generally the minimal denominator.

nmod_poly_mat_trace 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_poly_mat_det det A

Sets det to the determinant of the square matrix A. Uses a direct formula, fraction-free LU decomposition, or interpolation, depending on the size of the matrix.

nmod_poly_mat_det_fflu det A

Sets det to the determinant of the square matrix A. The determinant is computed by performing a fraction-free LU decomposition on a copy of A.

nmod_poly_mat_det_interpolate det A

Sets det to the determinant of the square matrix A. The determinant is computed by determining a bound \(n\) for its length, evaluating the matrix at \(n\) distinct points, computing the determinant of each coefficient matrix, and forming the interpolating polynomial.

If the coefficient ring does not contain \(n\) distinct points (that is, if working over \(\mathbf{Z}/p\mathbf{Z}\) where \(p < n\)), this function automatically falls back to nmod_poly_mat_det_fflu.

nmod_poly_mat_rank A

Returns the rank of A. Performs fraction-free LU decomposition on a copy of A.

nmod_poly_mat_inv Ainv den A

Sets (Ainv, den) to the inverse matrix of A. Returns 1 if A is nonsingular and 0 if A is singular. Aliasing of Ainv and A is allowed.

More precisely, det will be set to the determinant of A and Ainv will be set to the adjugate matrix of A. Note that the determinant is not necessarily the minimal denominator.

Uses fraction-free LU decomposition, followed by solving for the identity matrix.

nmod_poly_mat_nullspace res mat

Computes the right rational nullspace of the matrix mat and returns the nullity.

More precisely, assume that mat has rank \(r\) and nullity \(n\). Then this function sets the first \(n\) columns of res to linearly independent vectors spanning the nullspace of mat. As a result, we always have rank(res) \(= n\), and mat \(\times\) res is the zero matrix.

The computed basis vectors will not generally be in a reduced form. In general, the polynomials in each column vector in the result will have a nontrivial common GCD.

nmod_poly_mat_solve X den A B

Solves the equation \(AX = B\) for nonsingular \(A\). More precisely, computes (X, den) such that \(AX = B \times \operatorname{den}\). Returns 1 if \(A\) is nonsingular and 0 if \(A\) is singular. The computed denominator will not generally be minimal.

Uses fraction-free LU decomposition followed by fraction-free forward and back substitution.

nmod_poly_mat_solve_fflu X den A B

Solves the equation \(AX = B\) for nonsingular \(A\). More precisely, computes (X, den) such that \(AX = B \times \operatorname{den}\). Returns 1 if \(A\) is nonsingular and 0 if \(A\) is singular. The computed denominator will not generally be minimal.

Uses fraction-free LU decomposition followed by fraction-free forward and back substitution.

nmod_poly_mat_solve_fflu_precomp X perm FFLU B

Performs fraction-free forward and back substitution given a precomputed fraction-free LU decomposition and corresponding permutation.