nmod_mat.h

Initialises mat as a rows by cols matrix modulo $n$ with all entries zero. Requires $n \ge 1$. Throws an exception if $\mathit{rows} \cdot \mathit{cols}$ overflows an slong.

Initialises mat as a copy of src, with the same dimensions and modulus. The copy owns its entries even if src is a window.

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

Copies the entries of $A$ to $B$, which must have the same dimensions. The modulus of $B$ is not changed.

Swaps mat1 and mat2 in constant time by swapping their structs. Must not be used with windows, whose entries belong to another matrix.

Swaps the entries of two matrices of the same dimensions one by one. This works for windows.

Returns the modulus of mat.

Sets the modulus of mat to $n \ge 1$. The entries are not changed, so they must be reduced afterwards if they may exceed $n - 1$.

Returns, respectively sets, the entry in row $i$ and column $j$. x must be reduced.

Returns a pointer to the entry in row $i$ and column $j$, respectively to the first entry of row $i$. The entries of a row are contiguous; the next row starts mat->stride words later.

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

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

Initialises window as the submatrix of mat formed by rows $r_1$ to $r_2 - 1$ and columns $c_1$ to $c_2 - 1$, where $0 \le r_1 \le r_2 \le$ mat->r and $0 \le c_1 \le c_2 \le$ mat->c. The window shares its entries with mat, so writing to one changes the other.

Releases a window. This does nothing at present, but every window should be cleared for future compatibility.

Sets res to mat1 placed above mat2, respectively to the left of mat2. For an $m \times n$ matrix mat1, mat2 must be $k \times n$ and res $(m + k) \times n$, respectively mat2 $m \times k$ and res $m \times (n + k)$. res must not be aliased with the inputs.

Sets mat to the zero matrix, respectively to the matrix with ones on the main diagonal and zeros elsewhere. mat need not be square.

Returns 1 if the two matrices have the same dimensions and the same entries, and 0 otherwise. The moduli are not compared.

Returns 1 if mat is zero, if it has ones on the main diagonal and zeros elsewhere, or if its row $i$ is zero, respectively, and 0 otherwise. Empty matrices are both zero and one.

Sets the entries to independent integers chosen uniformly at random in $[0, n)$.

Sets each row with _nmod_vec_randtest: entries from n_randtest reduced modulo $n$, and with probability 1/2 a sparse row.

Sets the entries to independent integers chosen uniformly at random in $[1, n)$, so that no entry is zero.

Sets mat to $P D Q$ where $D$ is the matrix with $d_0, \ldots, d_{n-1}$ (the entries of diag) on the main diagonal and zeros elsewhere, and $P$ and $Q$ are random permutation matrices. Requires $n \le$ the number of rows and of columns. Returns the parity (0 for even, 1 for odd) of the two permutations combined.

Sets mat to a random matrix of the given rank, with exactly rank nonzero entries, each uniform in $[1, n)$ and no two in the same row or column. Throws an exception if rank is negative or exceeds a dimension. Follow with nmod_mat_randops to obtain a dense matrix of the same rank.

For a prime modulus, sets mat to a random matrix of rank $r$ = rank whose rank profile matrix has its $r$ nonzero entries at the positions (mrp_r[k], mrp_c[k]) for $0 \le k < r$, given in any order. Throws an exception if rank is negative or exceeds a dimension, or if two positions share a row or a column or one lies outside the matrix.

Performs count random elementary operations on mat, each adding or subtracting a row to or from another row, or a column to or from another column (operations whose two indices coincide are skipped). These operations have determinant 1, so the rank and, for square matrices, the determinant are preserved.

Sets mat to a random lower, respectively upper, triangular matrix. The entries strictly below (above) the diagonal are random, the diagonal entries are 1 if unit is nonzero and random nonzero values otherwise. mat need not be square.

Prints a header line with the dimensions and modulus, then one line per row, with the entries in brackets and right-aligned to the number of decimal digits of $n$. nmod_mat_fprint_pretty returns a positive value on success and a nonpositive value on a write error. Functions with a FILE argument are declared only if <stdio.h> is included before nmod_mat.h.

The same as nmod_mat_fprint_pretty, writing to stdout and f respectively.

Sets $B$ to the transpose of $A$. Throws an exception unless $B$ has as many rows as $A$ has columns and vice versa. $B$ may be aliased with $A$ if $A$ is square.

Writes the transpose of the $m \times n$ array $A$ (row stride Astride) to the $n \times m$ array $B$ (row stride Bstride). The words are copied as they are. The two arrays must not overlap.

Swaps rows (columns) $r$ and $s$ of mat. If perm is not NULL, entries $r$ and $s$ of the array perm are swapped as well.

Reverses the order of the rows (columns) of mat, that is, swaps rows (columns) $i$ and $r - 1 - i$ for $0 \le i < r/2$, where $r$ is the number of rows (columns). If perm is not NULL, the same permutation is applied to it.

Replaces row $i$ of mat by the old row perm_act[i], for every $i$, where perm_act is a permutation of the row indices. If perm_store is not NULL, it is updated in the same way: perm_store[i] becomes the old perm_store[perm_act[i]].

Sets $C = A + B$, respectively $C = A - B$. The three matrices must have the same dimensions.

Sets $B = -A$. The matrices must have the same dimensions.

Sets $B = cA$. Requires $c < n$.

Sets $B = cA$ for any integer $c$, which is first reduced modulo $n$.

Sets $C = A + cB$. Unlike nmod_mat_scalar_mul, $c$ may be any word; it is reduced modulo $n$ first. Uses Shoup multiplication under the same conditions as nmod_mat_scalar_mul.

Sets $C = AB$, where $A$ is $m \times k$, $B$ is $k \times n$ and $C$ is $m \times n$. $C$ may be aliased with $A$ or $B$.

Sets $D = C + AB$, respectively $D = C - AB$. $D$ may be aliased with $C$ but not with $A$ or $B$. The product is either computed by classical multiplication fused with the addition, or with nmod_mat_mul and then added; see Adding a product.

Sets $C = AB$ by classical multiplication, computing each entry as a dot product with a single reduction. $C$ must not be aliased with $A$ or $B$.

The same as nmod_mat_mul_classical, with the rows of $C$ distributed over the threads of FLINT's thread pool. Dimensions below 20 are handled by the serial code. $C$ must not be aliased with $A$ or $B$.

Sets $C = AB$ by one level of the Strassen–Winograd algorithm: seven products of half-size blocks, each computed by nmod_mat_mul (which may recurse), and 15 block additions. $C$ must not be aliased with $A$ or $B$.

Sets $C = AB$ by floating-point matrix multiplication with flint_sgemm or flint_dgemm, which use an external BLAS if FLINT was built with one and FLINT's own kernels otherwise. Returns 1 on success. Returns 0, and does nothing, if a dimension is 0 or exceeds INT_MAX, if the inner dimension is so large that no suitable set of at most 12 moduli exists, or on 32-bit machines. $C$ may be aliased with $A$ or $B$.

Sets $C = AB$ for a modulus $n \le 255$ (checked only by FLINT_ASSERT) using kernels for entries stored in bytes. $C$ may be aliased with $A$ or $B$. Uses several threads when available.

The multiplication of nmod_mat_mul_u8 on byte arrays: sets the $m \times n$ array $C$ to $AB$, where $A$ is $m \times k$ and $B$ is $k \times n$, each stored by rows with the given row strides (in bytes), with entries reduced modulo mod.n, which must be at most 255. $C$ may be equal to $A$ or $B$ (same pointer) but must not otherwise overlap them.

Sets $C = AB$ for a modulus $n < 2^{32}$ with an integer SIMD kernel (AVX-512, AVX2, NEON, or portable C), and returns 1. Returns 0 if $n \ge 2^{32}$ or on 32-bit machines. $C$ may be aliased with $A$ or $B$. Uses several threads when available.

The multiplication of nmod_mat_mul_u32 on arrays of 32-bit entries: $A$ is $m \times k$, $B$ is $k \times n$ and $C$ is $m \times n$, each stored by rows with the given row strides, with entries reduced modulo mod.n. Returns 0 if mod.n $\ge 2^{32}$ or on 32-bit machines and 1 otherwise. $C$ may be equal to $A$ or $B$ (same pointer and stride) but must not otherwise overlap them.

Sets $C = AB$ for a modulus $n \le 2^{52}$ with the AVX512-IFMA instructions, and returns 1. Returns 0 if $n > 2^{52}$, or if FLINT was not compiled for a processor with AVX512-IFMA (or on 32-bit machines). $C$ may be aliased with $A$ or $B$. Uses several threads when available.

Sets $C = AB$ for a modulus $n \le 2^{52}$ with integer SIMD instructions (AVX-512, AVX2, NEON, or portable C), and returns 1. Returns 0 if $n > 2^{52}$, on 32-bit machines, and for the portable C code compiled by MSVC. $C$ may be aliased with $A$ or $B$. Uses several threads when available.

Sets $C = AB$ for a modulus $n < 2^{50}$ in double precision, and returns

1. Returns 0 if $n \ge 2^{50}$, on 32-bit machines, and for the portable C code compiled by MSVC. $C$ may be aliased with $A$ or $B$. Uses several threads when available.

Sets $c = Ab$, where $A$ is $m \times k$ and $b$ is the vector of length blen, truncated or extended by zeros to length $k$. The $m$ entries of $c$ are written. In the _ptr version, entry $i$ of $b$ and $c$ is *b[i] and *c[i]. Each entry of $c$ is a dot product with one reduction. $c$ must not overlap $b$, except in the _ptr version, which copies.

Sets $c = aB$, where $B$ is $k \times n$ and $a$ is the vector of length alen, truncated or extended by zeros to length $k$. The $n$ entries of $c$ are written. In the _ptr version, entry $i$ of $a$ and $c$ is *a[i] and *c[i]. $c$ must not overlap $a$, except in the _ptr version, which copies.

Sets dest to mat raised to the power pow, by binary exponentiation. The matrix must be square; the power 0 gives the identity matrix. nmod_mat_pow allows dest to be aliased with mat; _nmod_mat_pow does not.

Returns the sum of the diagonal entries of the square matrix mat.

Sets $X = L^{-1} B$ for lower triangular $L$, respectively $X = U^{-1} B$ for upper triangular $U$. Uses substitution if $B$ has fewer than 64 rows or fewer than 64 columns, and the recursive algorithm otherwise.

Forward, respectively back, substitution, for an $r \times r$ triangular matrix. If $B$ has at least $\max(4, r/4)$ columns ($\max(4, r/2)$ for $n > 2^{31}$, or $n > 2^{15}$ with 32-bit words), the rows of $X$ are computed one after the other, each as the row of $B$ minus a linear combination of the rows already computed, with delayed reductions: the products are accumulated by vectors in one, two or three words and each entry is reduced once (or a few times, for some moduli below $2^{32}$). Otherwise each column of $X$ is computed entry by entry, each entry with one dot product and one reduction, which is faster with few long columns. The inverses of the diagonal entries are computed once.

Splits $L$ (or $U$) into blocks of $\lfloor r/2 \rfloor$ and $\lceil r/2 \rceil$ rows and solves recursively, reducing the work to matrix multiplications.

Sets $X = B L^{-1}$ for lower triangular $L$, respectively $X = B U^{-1}$ for upper triangular $U$. Uses substitution if $B$ has fewer than 64 rows or fewer than 64 columns, and the recursive algorithm otherwise.

Substitution, for an $r \times r$ triangular matrix, with three methods. If $B$ has at least $\max(6, r/4)$ rows ($\max(6, r/2)$ for $n > 2^{31}$, or $n > 2^{15}$ with 32-bit words), as nmod_mat_solve_tril_classical (nmod_mat_solve_triu_classical) with delayed reductions on the transposed system, $B$ being transposed by blocks of 256 rows. Otherwise, if $r \le 128$ ($r \le 64$ for these larger moduli) or $B$ has at most 4 rows, each row $x$ of $X$ is computed from the last entry to the first for $L$ (from the first to the last for $U$): once $x_j$ is known, $x_j$ times the row $j$ of the triangular matrix is added to the unreduced sums of the remaining entries, each reduced once. Otherwise (a large triangular matrix and a few rows), each entry is computed with one dot product and one reduction, the columns of the triangular matrix being copied to rows 64 at a time so that the dot products read contiguous memory. The inverses of the diagonal entries are computed once.

Splits $L$ (or $U$) into blocks of $\lfloor r/2 \rfloor$ and $\lceil r/2 \rceil$ rows and columns and solves recursively, reducing the work to matrix multiplications.

Computes an LU decomposition with row pivoting of the $m \times n$ matrix $A$ modulo a prime, overwriting $A$ with $L$ and $U$, and returns the rank $r$. On return, row $i$ of $LU$ is row P[i] of the original $A$, where P is an array of length $m$ (it need not be initialised). $U$ is in row echelon form with $r$ nonzero rows, and $L$ is $m \times r$ unit lower triangular. If rank_check is nonzero, the function may stop as soon as it finds that the rank is less than $n$, and then returns 0 and leaves $A$ undefined.

The same as nmod_mat_lu with rank_check 0, and in addition writes to pivots_nonpivots, an array of length $n$, the indices of the $r$ pivot columns of $U$ in increasing order followed by the indices of the $n - r$ other columns in increasing order.

Computes the PLE decomposition of the $m \times n$ matrix $A$ modulo a prime that reveals its rank profile matrix, overwrites $A$ with $L$ and $E$ in the storage of nmod_mat_lu, and returns the rank $r$. Row $i$ of $LE$ is row P[i] of the original $A$ (P has length $m$). The array pivots_nonpivots, of length $n$, receives the pivot columns of $E$ followed by the other columns, both in increasing order; it may be NULL. The rows P[r], ..., P[m-1] are also in increasing order, and the rank profile matrix of $A$ has its nonzero entries at (P[k], pivots_nonpivots[k]) for $k < r$. If flags contains NMOD_MAT_PLE_RANK_CHECK and the rank is less than $\min(m, n)$, the function returns 0, possibly before the end, and leaves A, P and pivots_nonpivots undefined.

Given the output LU, P, pivots_nonpivots and rank $= r$ of nmod_mat_ple for an $m \times n$ matrix $A$, sets the $n \times (n - r)$ matrix $X$ to the basis of the right nullspace $\{x : Ax = 0\}$ computed by nmod_mat_nullspace, respectively the $(m - r) \times m$ matrix $X$ to the basis of the left nullspace $\{x : xA = 0\}$ computed by nmod_mat_left_nullspace. $X$ must have exactly these dimensions.

The same bases without their identity matrix. For the right nullspace, $X$ is $r \times (n - r)$ and receives $C$: its row $j$ gives the entries in position pivots_nonpivots[j] and its column $k$ corresponds to the vector with a 1 in position pivots_nonpivots[r+k]. For the left nullspace, $X$ is $(m - r) \times r$, rows (length $m$) receives the row rank profile of $A$ in increasing order followed by the other rows in increasing order, and $X$ receives the columns of $D$ sorted accordingly: its column $j$ gives the entries in position rows[j] and its row $k$ corresponds to the vector with a 1 in position rows[r+k].

Solves $AX = B$ for a square matrix $A$. If $A$ is nonsingular, sets $X$ to the unique solution and returns 1. Otherwise returns 0 and leaves $X$ unchanged. $X$ may be aliased with $A$ or $B$.

Solves $Ax = b$ for a square $m \times m$ matrix $A$ and vectors $x$, $b$ of length $m$, as nmod_mat_solve. $x$ may be equal to $b$.

Decides whether $AX = B$ has a solution for an arbitrary $m \times n$ matrix $A$ and $m \times c$ matrix $B$. If so, sets the $n \times c$ matrix $X$ to a solution and returns 1; otherwise sets $X$ to zero and returns 0. Returns 0 if the dimensions are incompatible. $X$ may be aliased with $B$ but not with $A$.

The same as nmod_mat_can_solve, and in addition, for each pointer that is not NULL, stores the rank of $A$ in *rank, the row permutation of the LU decomposition of $A$ in perm (length $m$), and the indices of the pivot columns in the first *rank entries of pivots (length at least $\min(m, n)$).

Returns the determinant of the square matrix $A$, for any modulus. Throws an exception if $A$ is not square.

Returns the determinant of the square matrix $A$, for any modulus, by triangularising $A$ with Euclidean row operations. Throws an exception if $A$ is not square.

Returns the rank of $A$, which may have any shape. The modulus must be prime.

If the square matrix $A$ is invertible, sets $B = A^{-1}$ and returns 1. Otherwise returns 0, and the entries of $B$ are unspecified. The modulus must be prime. $B$ may be aliased with $A$.

Puts $A$ in reduced row echelon form and returns its rank.

Sets the first $d$ columns of $X$ to a basis of the right nullspace $\{x : Ax = 0\}$ of the $m \times n$ matrix $A$, sets the other entries of $X$ to zero, and returns the nullity $d = n - \operatorname{rank}(A)$. $X$ must have $n$ rows and at least $d$ columns; $n \times n$ always suffices. $X$ may be aliased with $A$. The basis is the one with an identity matrix in the rows of the columns of $A$ without pivot, computed with nmod_mat_ple and nmod_mat_ple_nullspace.

Sets the first $d$ rows of $X$ to a basis of the left nullspace $\{v : vA = 0\}$ of the $m \times n$ matrix $A$, sets the other entries of $X$ to zero, and returns the nullity $d = m - \operatorname{rank}(A)$. $X$ must have at least $d$ rows and $m$ columns; $m \times m$ always suffices. The basis is the one with an identity matrix in the columns of the rows of $A$ that are not in its row rank profile, computed with nmod_mat_ple and nmod_mat_ple_left_nullspace.

Reduces row $m$ of $M$ against rows that are already reduced, for incremental Gaussian elimination, and returns the column of its new pivot, or $-1$ if it reduces to zero.

Puts $A$ in strong echelon form, using the algorithm of [FieHof2014]. $A$ must have at least as many rows as columns; add zero rows otherwise.

Puts $A$ in Howell form [StoMul1998] and returns the number $k$ of nonzero rows, which come first. $A$ must have at least as many rows as columns.

Sets $p$ to the characteristic polynomial $\det(xI - M)$ of the square matrix $M$. An exception is thrown if $M$ is not square. nmod_mat_charpoly and the division-free _berkowitz work for any modulus. _danilevsky returns 1 on success and 0 if it needs an inverse that does not exist, which cannot happen for a prime modulus. For $n = 1$ the result is the zero polynomial.

Sets $p$ to the minimal polynomial of the square matrix $M$, the monic polynomial of least degree with $p(M) = 0$, and throws an exception if $M$ is not square. The modulus must be prime. If P is not NULL, nmod_mat_minpoly_with_gens sets P[j] to 1 for each index $j$ such that the unit vector $e_j$ was used as a Krylov generator, and leaves the other entries of the array (of length $r$) unchanged.

Replaces the square matrix $M$ by $P^{-1} M P$, where $P$ is the identity matrix with the entries in row $r$ and every column $j \notin \{r-1, r\}$ replaced by $d$. Requires $d < n$.

Sets $D = AB$ if op is 0, $D = C + AB$ if op is 1 and $D = C - AB$ if op is $-1$, by the classical algorithm of nmod_mat_mul_classical. $D$ may be aliased with $C$ but not with $A$ or $B$. $C$ is not read if op is 0.

The threaded version of _nmod_mat_mul_classical_op, using the num_threads threads in threads, obtained from flint_request_threads, in addition to the calling thread. If $k = 0$ or the modulus is 1, $D$ is not written.

Sets $B = cA$ with nmod_mul, respectively with n_mulmod_shoup and c_pr = n_mulmod_precomp_shoup(c, n), which requires $n < 2^{\mathtt{FLINT\_BITS} - 1}$. Both require $c < n$.

Sets $C = A + cB$, as the two functions above. Both require $c < n$.

Returns the determinant of the square matrix $A$ modulo a prime, computed by nmod_mat_lu, which destroys $A$.

Returns the determinant of the square matrix $A$ for any modulus, as nmod_mat_det_howell, destroying $A$.

Puts $A$ in reduced row echelon form and returns the rank $r$, as nmod_mat_rref, and in addition stores in pivots_nonpivots (length the number of columns) the pivot columns followed by the other columns, and in P (length the number of rows) the row permutation of the LU decomposition used.

Writes the $r + 1$ coefficients of the characteristic polynomial of the $r \times r$ matrix $M$ to p, by Berkowitz's algorithm. Works for any modulus.