fq_mat.h – matrices over finite fields¶
Description.
Memory management¶
-
void
fq_mat_init
(fq_mat_t mat, slong rows, slong cols, const fq_ctx_t ctx)¶ Initialises
mat
to arows
-by-cols
matrix with coefficients in \(\mathbf{F}_{q}\) given byctx
. All elements are set to zero.
-
void
fq_mat_init_set
(fq_mat_t mat, fq_mat_t src, const fq_ctx_t ctx)¶ Initialises
mat
and sets its dimensions and elements to those ofsrc
.
Basic properties and manipulation¶
-
fq_struct *
fq_mat_entry
(fq_mat_t mat, slong i, slong j)¶ Directly accesses the entry in
mat
in row \(i\) and column \(j\), indexed from zero. No bounds checking is performed.
-
fq_struct *
fq_mat_entry_set
(fq_mat_t mat, slong i, slong j, fq_t x, const fq_ctx_t ctx)¶ Sets the entry in
mat
in row \(i\) and column \(j\) tox
.
Concatenate¶
-
void fq_mat_concat_vertical(fq_mat_t res, const fq_mat_t mat1, const fq_mat_t mat2, const fq_ctx_t ctx) Sets code{res} to vertical concatenation of (code{mat1}, code{mat2}) in that order. Matrix dimensions : code{mat1} : $m times n$, code{mat2} : $k times n$, code{res} : $(m + k) times n$.
-
void fq_mat_concat_horizontal(fq_mat_t res, const fq_mat_t mat1, const fq_mat_t mat2, const fq_ctx_t ctx) Sets code{res} to horizontal concatenation of (code{mat1}, code{mat2}) in that order. Matrix dimensions : code{mat1} : $m times n$, code{mat2} : $m times k$, code{res} : $m times (n + k)$.
Printing¶
-
void
fq_mat_print_pretty
(const fq_mat_t mat, const fq_ctx_t ctx)¶ Pretty-prints
mat
tostdout
. A header is printed followed by the rows enclosed in brackets.
-
int
fq_mat_fprint_pretty
(FILE * file, const fq_mat_t mat, const fq_ctx_t ctx)¶ Pretty-prints
mat
tofile
. A header is printed followed by the rows enclosed in brackets.In case of success, returns a positive value. In case of failure, returns a non-positive value.
Window¶
-
void
fq_mat_window_init
(fq_mat_t window, const fq_mat_t mat, slong r1, slong c1, slong r2, slong c2, const fq_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
.
Random matrix generation¶
-
void
fq_mat_randtest
(fq_mat_t mat, flint_rand_t state, const fq_ctx_t ctx)¶ Sets the elements of
mat
to random elements of \(\mathbf{F}_{q}\), given byctx
.
-
int
fq_mat_randpermdiag
(fq_mat_t mat, fq_struct * diag, slong n, flint_rand_t state, const fq_ctx_t ctx)¶ Sets
mat
to a random permutation of the diagonal matrix with \(n\) leading entries given by the vectordiag
. It is assumed that the main diagonal ofmat
has room for at least \(n\) entries.Returns \(0\) or \(1\), depending on whether the permutation is even or odd respectively.
-
void
fq_mat_randrank
(fq_mat_t mat, slong rank, flint_rand_t state, const fq_ctx_t ctx)¶ 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 elements of \(\mathbf{F}_{q}\).The matrix can be transformed into a dense matrix with unchanged rank by subsequently calling
fq_mat_randops()
.
-
void
fq_mat_randops
(fq_mat_t mat, slong count, flint_rand_t state, const fq_ctx_t ctx)¶ Randomises
mat
by performing elementary row or column operations. More precisely, at mostcount
random additions or subtractions of distinct rows and columns will be performed. This leaves the rank (and for square matrices, determinant) unchanged.
Comparison¶
-
int
fq_mat_equal
(fq_mat_t mat1, fq_mat_t mat2, const fq_ctx_t ctx)¶ Returns nonzero if mat1 and mat2 have the same dimensions and elements, and zero otherwise.
-
int
fq_mat_is_zero
(const fq_mat_t mat, const fq_ctx_t ctx)¶ Returns a non-zero value if all entries
mat
are zero, and otherwise returns zero.
Addition and subtraction¶
-
void
fq_mat_add
(fq_mat_t C, const fq_mat_t A, const fq_mat_t B, const fq_ctx_t ctx)¶ Computes \(C = A + B\). Dimensions must be identical.
Matrix multiplication¶
-
void
fq_mat_mul
(fq_mat_t C, const fq_mat_t A, const fq_mat_t B, const fq_ctx_t ctx)¶ Sets \(C = AB\). Dimensions must be compatible for matrix multiplication. \(C\) is not allowed to be aliased with \(A\) or \(B\). This function automatically chooses between classical and KS multiplication.
-
void
fq_mat_mul_classical
(fq_mat_t C, const fq_mat_t A, const fq_mat_t B, const fq_ctx_t ctx)¶ 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.
Inverse¶
LU decomposition¶
-
slong
fq_mat_lu
(slong * P, fq_mat_t A, int rank_check, const fq_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.This function calls
fq_mat_lu_recursive
.
-
slong
fq_mat_lu_classical
(slong * P, fq_mat_t A, int rank_check, const fq_ctx_t ctx)¶ Computes a generalised LU decomposition \(LU = PA\) of a given matrix \(A\), returning the rank of \(A\). The behavior of this function is identical to that of
fq_mat_lu
. Uses Gaussian elimination.
-
slong
fq_mat_lu_recursive
(slong * P, fq_mat_t A, int rank_check, const fq_ctx_t ctx)¶ Computes a generalised LU decomposition \(LU = PA\) of a given matrix \(A\), returning the rank of \(A\). The behavior of this function is identical to that of
fq_mat_lu
. Uses recursive block decomposition, switching to classical Gaussian elimination for sufficiently small blocks.
Reduced row echelon form¶
-
slong
fq_mat_rref
(fq_mat_t A, const fq_ctx_t ctx)¶ 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.
-
slong
fq_mat_reduce_row
(fq_mat_t A, slong * P, slong * L, slong n, const fq_ctx_t ctx)¶ 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.
Triangular solving¶
-
void
fq_mat_solve_tril
(fq_mat_t X, const fq_mat_t L, const fq_mat_t B, int unit, const fq_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.
-
void
fq_mat_solve_tril_classical
(fq_mat_t X, const fq_mat_t L, const fq_mat_t B, int unit, const fq_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. Uses forward substitution.
-
void
fq_mat_solve_tril_recursive
(fq_mat_t X, const fq_mat_t L, const fq_mat_t B, int unit, const fq_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.Uses the block inversion formula
`` 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} ``
to reduce the problem to matrix multiplication and triangular solving of smaller systems.
-
void
fq_mat_solve_triu
(fq_mat_t X, const fq_mat_t U, const fq_mat_t B, int unit, const fq_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.
-
void
fq_mat_solve_triu_classical
(fq_mat_t X, const fq_mat_t U, const fq_mat_t B, int unit, const fq_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. Uses forward substitution.
-
void
fq_mat_solve_triu_recursive
(fq_mat_t X, const fq_mat_t U, const fq_mat_t B, int unit, const fq_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.Uses the block inversion formula
`` 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} ``
to reduce the problem to matrix multiplication and triangular solving of smaller systems.
Nonsingular square solving¶
Transforms¶
-
void
fq_mat_similarity
(fq_mat_t M, slong r, fq_t d, fq_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.