nmod_poly_mat.h

Initialises mat as a rows by cols matrix of zero polynomials modulo n. Throws if \mathit{rows} \cdot \mathit{cols} overflows an slong.

Initialises mat as a copy of src, with the same modulus.

Frees the memory used by mat. Must not be called on a window.

Swaps two matrices in constant time by swapping their structs (not for windows), respectively swaps the entries of two matrices of the same dimensions one by one.

Returns a pointer to the entry in row i and column j.

Returns the number of rows, respectively columns, of mat.

Returns the modulus n of mat.

Returns 1 if mat has no rows or no columns, respectively as many rows as columns, and 0 otherwise.

Returns the largest length of an entry (0 if all entries are zero), respectively the largest degree, which is the largest length minus one (-1 for the zero matrix).

Sets the matrix coeff to the coefficients of x^{\mathit{deg}} of the entries of pmat, respectively sets these coefficients of pmat to the entries of coeff. The dimensions must agree.

Sets pmat to the constant matrix cmat, which must have the same dimensions.

Returns 1 if pmat is the constant matrix cmat (same dimensions, all entries constant and equal), and 0 otherwise.

Sets res to pmat with every entry truncated to length len (reduced modulo x^{\mathit{len}}), respectively truncates pmat in place.

Sets res to pmat multiplied by x^k, respectively divided by x^k with the coefficients of degree less than k discarded. Aliasing is allowed.

Initialises window as the submatrix of mat formed by rows r_1 to r_2 - 1 and columns c_1 to c_2 - 1, sharing its entries and modulus with mat.

Releases a window. This does nothing at present.

Sets res to mat1 placed to the left of, respectively above, mat2, whose dimensions must be compatible.

Prints mat to stdout: a header <r x c matrix over Z/nZ[x]> (with the variable name x), then each row in square brackets with the entries printed by nmod_poly_print (length, modulus and coefficients) and separated by commas, then an empty line.

Sets each entry to a random polynomial of length up to len, with uniformly random coefficients (nmod_poly_rand), respectively with a bias towards special values (nmod_poly_randtest).

Sets each entry, with probability density, to a random polynomial of length up to len, and to zero otherwise.

Returns 1 if the matrices have the same dimensions and entries, and 0 otherwise.

Returns 1 if mat is zero, respectively has the constant 1 on the main diagonal and zeros elsewhere, and 0 otherwise.

Sets mat to the zero matrix, respectively to the matrix with the constant 1 on the main diagonal and zeros elsewhere.

Copies mat2 to mat1, which must have the same dimensions.

Sets B to the transpose of A; B may be A if it is square. Throws if the dimensions are incompatible.

Sets the matrix B over \mathbb{Z}/n\mathbb{Z} to A evaluated at x.

Sets C = A + B, C = A - B, respectively B = -A. Aliasing is allowed.

Sets B = cA for a polynomial, respectively a reduced constant, c. Aliasing is allowed.

Sets trace to the sum of the diagonal entries of the square matrix mat.

Sets C = AB, choosing between the methods below from the dimensions, the lengths of the entries and the modulus. C may be A or B. See Choice.

Sets C = AB by sums of polynomial products, respectively by Kronecker substitution: the entries are packed into integers with nmod_poly_bit_pack, multiplied with fmpz_mat_mul and unpacked. C may be A or B.

Sets C = AB by evaluating A and B at L = \ell_A + \ell_B - 1 points (where \ell_A, \ell_B are the largest lengths of the entries), multiplying the L pairs of matrices over \mathbb{Z}/n\mathbb{Z} with nmod_mat_mul and interpolating. Requires n to be a prime with n \ge L; throws if n < L.

Sets each entry of C to the coefficients of degrees z_l to z_h - 1 of the corresponding entry of AB (the product shifted right by z_l and truncated to length z_h - z_l), and returns 1; returns 0 if the small-prime FFT is not available or no transform plan admits the size of the accumulated products, in which case C may be partially written. C may be A or B.

Sets B = A^2 for a square matrix A; B may be A. The classical version uses five polynomial products for 2 \times 2 matrices; the others are the squaring versions of the multiplication methods. nmod_poly_mat_sqr uses the classical algorithm for dimension less than 10. Above, it uses evaluation and interpolation for a prime modulus of more than \beta/4 bits that is at least 2\ell - 1, where \ell is the largest length of an entry, and dimension above 80 + \sqrt{\ell}; otherwise Kronecker substitution, or the classical algorithm for entries of length above 128.

Sets B = A^{\mathit{exp}} for a square matrix A by binary powering. A^0 is the identity. B may be A but must not be a window.

Returns the index of a row r with start_row \le r < end_row whose entry in column c is nonzero, or -1 if there is none: the first such row, respectively one whose entry has least length.

Computes a fraction-free LU decomposition of A in B and returns the rank r of A over the field of rational functions. den is set to the last pivot, a nonzero r \times r minor of A (1 if r = 0). Row exchanges are applied to perm if it is not NULL; pivots are chosen with nmod_poly_mat_find_pivot_partial. If rank_check is set, the function returns 0 with den = 0 as soon as a column without pivot is found. B may be A. See Fraction-free elimination.

Sets (B, den) to the reduced row echelon form of A over the field of rational functions and returns the rank: B/\mathit{den} is in reduced row echelon form, with den on the pivot positions. B may be A.

Sets det to the determinant of the square matrix A. nmod_poly_mat_det_fflu uses fraction-free elimination; nmod_poly_mat_det_interpolate evaluates A at the points 0, 1, \ldots, L - 1 with L = n(\ell - 1) + 1, where \ell is the largest length of an entry, computes the determinants with nmod_mat_det and interpolates, falling back to fraction-free elimination if L exceeds the modulus. nmod_poly_mat_det uses explicit formulas for n \le 2, fraction-free elimination for n < 15 and interpolation otherwise. The modulus must be prime for n \ge 3.

Returns the rank of A over the field of rational functions, computed by fraction-free elimination. Requires a prime modulus.

For a square A of dimension n and an n \times k matrix B, sets (X, den) with AX = \mathit{den} \cdot B and \mathit{den} = \det A, and returns 1 if A is nonsingular; returns 0 with den = 0 if A is singular. Both use fraction-free elimination. X may be A but not B.

Solves AX = \mathit{den} \cdot B given the output FFLU, den, perm of nmod_poly_mat_fflu for a nonsingular A, with fraction-free forward and back substitution. The sign of the permutation is not taken into account. perm must not be NULL, and X must not be B.

Sets (Ainv, den) to the inverse of the square matrix A, so that A \cdot \mathit{Ainv} = \mathit{den} \cdot I with \mathit{den} = \det A, and returns 1 if A is nonsingular; returns 0 if it is singular. Ainv may be A.

Sets the first n - r columns of the n \times n matrix res to a basis of the right nullspace of the m \times n matrix mat over the field of rational functions, with polynomial entries, and returns n - r; the other columns are set to zero.