fmpz_mod_mat.h – matrices over integers mod n¶
Types, macros and constants¶
-
type fmpz_mod_mat_struct¶
-
type fmpz_mod_mat_t¶
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 columnj
ofmat
.
-
void fmpz_mod_mat_set_entry(fmpz_mod_mat_t mat, slong i, slong j, const fmpz_t val, const fmpz_mod_ctx_t ctx)¶
Set the entry at row
i
and columnj
ofmat
toval
.
Memory management¶
-
void fmpz_mod_mat_init(fmpz_mod_mat_t mat, slong rows, slong cols, const fmpz_mod_ctx_t ctx)¶
Initialise
mat
as a matrix with the given number ofrows
andcols
and modulus defined byctx
.
-
void fmpz_mod_mat_init_set(fmpz_mod_mat_t mat, const fmpz_mod_mat_t src, const fmpz_mod_ctx_t ctx)¶
Initialise
mat
and set it equal to the matrixsrc
, including the number of rows and columns and the modulus.
-
void fmpz_mod_mat_clear(fmpz_mod_mat_t mat, const fmpz_mod_ctx_t ctx)¶
Clear
mat
and release any memory it used.
Basic manipulation ——————————————————————————–
-
slong fmpz_mod_mat_nrows(const fmpz_mod_mat_t mat, const fmpz_mod_ctx_t ctx)¶
Return the number of rows of
mat
.
-
slong fmpz_mod_mat_ncols(const fmpz_mod_mat_t mat, const fmpz_mod_ctx_t ctx)¶
Return the number of columns of
mat
.
-
void _fmpz_mod_mat_set_mod(fmpz_mod_mat_t mat, const fmpz_t n, const fmpz_mod_ctx_t ctx)¶
Set the modulus of the matrix
mat
ton
.
-
void fmpz_mod_mat_one(fmpz_mod_mat_t mat, const fmpz_mod_ctx_t ctx)¶
Set
mat
to the identity matrix (ones down the diagonal).
-
void fmpz_mod_mat_zero(fmpz_mod_mat_t mat, const fmpz_mod_ctx_t ctx)¶
Set
mat
to the zero matrix.
-
void fmpz_mod_mat_swap(fmpz_mod_mat_t mat1, fmpz_mod_mat_t mat2, const fmpz_mod_ctx_t ctx)¶
Efficiently swap the matrices
mat1
andmat2
.
-
void fmpz_mod_mat_swap_entrywise(fmpz_mod_mat_t mat1, fmpz_mod_mat_t mat2, const fmpz_mod_ctx_t ctx)¶
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, const fmpz_mod_ctx_t ctx)¶
Return \(1\) if
mat
has either zero rows or columns.
-
int fmpz_mod_mat_is_square(const fmpz_mod_mat_t mat, const fmpz_mod_ctx_t ctx)¶
Return \(1\) if
mat
has the same number of rows and columns.
-
void _fmpz_mod_mat_reduce(fmpz_mod_mat_t mat, const fmpz_mod_ctx_t ctx)¶
Reduce all the entries of
mat
by the modulusn
. This function is only needed internally.
Random generation¶
-
void fmpz_mod_mat_randtest(fmpz_mod_mat_t mat, flint_rand_t state, const fmpz_mod_ctx_t ctx)¶
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, const fmpz_mod_ctx_t ctx)¶
Initializes the matrix
window
to be anr2 - r1
byc2 - c1
submatrix ofmat
whose(0, 0)
entry is the(r1, c1)
entry ofmat
. The memory for the elements ofwindow
is shared withmat
.
-
void fmpz_mod_mat_window_clear(fmpz_mod_mat_t window, const fmpz_mod_ctx_t ctx)¶
Clears the matrix
window
and releases any memory that it uses. Note that the memory to the underlying matrix thatwindow
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, const fmpz_mod_ctx_t ctx)¶
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, const fmpz_mod_ctx_t ctx)¶
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, const fmpz_mod_ctx_t ctx)¶
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, const fmpz_mod_ctx_t ctx)¶
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, const fmpz_mod_ctx_t ctx)¶
Set
B
to equalA
.
-
void fmpz_mod_mat_transpose(fmpz_mod_mat_t B, const fmpz_mod_mat_t A, const fmpz_mod_ctx_t ctx)¶
Set
B
to the transpose ofA
.
Conversions¶
-
void fmpz_mod_mat_set_fmpz_mat(fmpz_mod_mat_t A, const fmpz_mat_t B, const fmpz_mod_ctx_t ctx)¶
Set
A
to the matrixB
reducing modulo the modulus ofA
.
-
void fmpz_mod_mat_get_fmpz_mat(fmpz_mat_t A, const fmpz_mod_mat_t B, const fmpz_mod_ctx_t ctx)¶
Set
A
to a lift ofB
.
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, const fmpz_mod_ctx_t ctx)¶
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, const fmpz_mod_ctx_t ctx)¶
Set
C
to \(A - B\).
-
void fmpz_mod_mat_neg(fmpz_mod_mat_t B, const fmpz_mod_mat_t A, const fmpz_mod_ctx_t ctx)¶
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, const fmpz_mod_ctx_t ctx)¶
Set
B
to \(cA\) wherec
is a constant.
-
void fmpz_mod_mat_scalar_mul_ui(fmpz_mod_mat_t B, const fmpz_mod_mat_t A, ulong c, const fmpz_mod_ctx_t ctx)¶
Set
B
to \(cA\) wherec
is a constant.
-
void fmpz_mod_mat_scalar_mul_fmpz(fmpz_mod_mat_t B, const fmpz_mod_mat_t A, fmpz_t c, const fmpz_mod_ctx_t ctx)¶
Set
B
to \(cA\) wherec
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, const fmpz_mod_ctx_t ctx)¶
Set
C
toA\times B
. The number of rows ofB
must match the number of columns ofA
.
-
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, const fmpz_mod_ctx_t ctx)¶
Set
D
toA\times B + op*C
whereop
is+1
,-1
or0
.
-
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, const fmpz_mod_ctx_t ctx)¶
Set
D
toA\times B + op*C
whereop
is+1
,-1
or0
.
-
void fmpz_mod_mat_mul_classical_threaded(fmpz_mod_mat_t C, const fmpz_mod_mat_t A, const fmpz_mod_mat_t B, const fmpz_mod_ctx_t ctx)¶
Set
C
toA\times B
. The number of rows ofB
must match the number of columns ofA
.
-
void fmpz_mod_mat_sqr(fmpz_mod_mat_t B, const fmpz_mod_mat_t A, const fmpz_mod_ctx_t ctx)¶
Set
B
toA^2
. The matrixA
must be square.
-
void fmpz_mod_mat_mul_fmpz_vec(fmpz *c, const fmpz_mod_mat_t A, const fmpz *b, slong blen, const fmpz_mod_ctx_t ctx)¶
-
void fmpz_mod_mat_mul_fmpz_vec_ptr(fmpz *const *c, const fmpz_mod_mat_t A, const fmpz *const *b, slong blen, const fmpz_mod_ctx_t ctx)¶
Compute a matrix-vector product of
A
and(b, blen)
and store the result inc
. The vector(b, blen)
is either truncated or zero-extended to the number of columns ofA
. The number entries written toc
is always equal to the number of rows ofA
.
-
void fmpz_mod_mat_fmpz_vec_mul(fmpz *c, const fmpz *a, slong alen, const fmpz_mod_mat_t B, const fmpz_mod_ctx_t ctx)¶
-
void fmpz_mod_mat_fmpz_vec_mul_ptr(fmpz *const *c, const fmpz *const *a, slong alen, const fmpz_mod_mat_t B, const fmpz_mod_ctx_t ctx)¶
Compute a vector-matrix product of
(a, alen)
andB
and and store the result inc
. The vector(a, alen)
is either truncated or zero-extended to the number of rows ofB
. The number entries written toc
is always equal to the number of columns ofB
.
Trace¶
-
void fmpz_mod_mat_trace(fmpz_t trace, const fmpz_mod_mat_t mat, const fmpz_mod_ctx_t ctx)¶
Set
trace
to the trace of the matrixmat
.
Gaussian elimination¶
-
void fmpz_mod_mat_det(fmpz_t res, const fmpz_mod_mat_t mat, const fmpz_mod_ctx_t ctx)¶
Set
res
to the determinant of the matrixmat
.
-
slong fmpz_mod_mat_rref(fmpz_mod_mat_t res, const fmpz_mod_mat_t mat, const fmpz_mod_ctx_t ctx)¶
Sets
res
to the reduced row echelon form ofmat
and returns the rank.The modulus is assumed to be prime.
Strong echelon form and Howell form¶
-
void fmpz_mod_mat_strong_echelon_form(fmpz_mod_mat_t mat, const fmpz_mod_ctx_t ctx)¶
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, const fmpz_mod_ctx_t ctx)¶
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.
Inverse¶
-
int fmpz_mod_mat_inv(fmpz_mod_mat_t B, const fmpz_mod_mat_t A, const fmpz_mod_ctx_t ctx)¶
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.
The modulus is assumed to be prime.
LU decomposition¶
-
slong fmpz_mod_mat_lu(slong *P, fmpz_mod_mat_t A, int rank_check, const fmpz_mod_ctx_t ctx)¶
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 modulus is assumed to be prime.
Triangular solving¶
-
void fmpz_mod_mat_solve_tril(fmpz_mod_mat_t X, const fmpz_mod_mat_t L, const fmpz_mod_mat_t B, int unit, const fmpz_mod_ctx_t ctx)¶
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.The modulus is assumed to be prime.
-
void fmpz_mod_mat_solve_triu(fmpz_mod_mat_t X, const fmpz_mod_mat_t U, const fmpz_mod_mat_t B, int unit, const fmpz_mod_ctx_t ctx)¶
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.The modulus is assumed to be prime.
Solving¶
-
int fmpz_mod_mat_solve(fmpz_mod_mat_t X, const fmpz_mod_mat_t A, const fmpz_mod_mat_t B, const fmpz_mod_ctx_t ctx)¶
Solves the matrix-matrix equation \(AX = B\).
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.
The modulus is assumed to be prime.
-
int fmpz_mod_mat_can_solve(fmpz_mod_mat_t X, const fmpz_mod_mat_t A, const fmpz_mod_mat_t B, const fmpz_mod_ctx_t ctx)¶
Solves the matrix-matrix equation \(AX = B\) over \(Fp\).
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.
The modulus is assumed to be prime.
Transforms¶
-
void fmpz_mod_mat_similarity(fmpz_mod_mat_t M, slong r, fmpz_t d, const fmpz_mod_ctx_t ctx)¶
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.
The modulus is assumed to be prime.
Characteristic polynomial¶
-
void fmpz_mod_mat_charpoly(fmpz_mod_poly_t p, const fmpz_mod_mat_t M, const fmpz_mod_ctx_t ctx)¶
Compute the characteristic polynomial \(p\) of the matrix \(M\). The matrix is required to be square, otherwise an exception is raised.
Minimal polynomial¶
-
void fmpz_mod_mat_minpoly(fmpz_mod_poly_t p, const fmpz_mod_mat_t M, const fmpz_mod_ctx_t ctx)¶
Compute the minimal polynomial \(p\) of the matrix \(M\). The matrix is required to be square, otherwise an exception is raised.
The modulus is assumed to be prime.