Safe Haskell | Safe-Inferred |
---|---|
Language | Haskell2010 |
- Matrices over finite fields (word-size characteristic)
- Memory management
- Basic properties and manipulation
- Conversions
- Concatenate
- Printing
- Window
- Random matrix generation
- Comparison
- Addition and subtraction
- Matrix multiplication
- Inverse
- LU decomposition
- Reduced row echelon form
- Triangular solving
- Solving
- Transforms
- Characteristic polynomial
- Minimal polynomial
An FqNModMat
represents an matrix over a finite field (word-size
characteristic). This module implements operations on matrices over a
finite field.
Synopsis
- data FqNModMat = FqNModMat !(ForeignPtr CFqNModMat)
- data CFqNModMat = CFqNModMat (Ptr CFqNMod) CLong CLong (Ptr (Ptr CFqNMod))
- newFqNModMat :: CLong -> CLong -> FqNModCtx -> IO FqNModMat
- withFqNModMat :: FqNModMat -> (Ptr CFqNModMat -> IO a) -> IO (FqNModMat, a)
- fq_nmod_mat_init :: Ptr CFqNModMat -> CLong -> CLong -> Ptr CFqNModCtx -> IO ()
- fq_nmod_mat_init_set :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModCtx -> IO ()
- fq_nmod_mat_clear :: Ptr CFqNModMat -> Ptr CFqNModCtx -> IO ()
- fq_nmod_mat_set :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModCtx -> IO ()
- fq_nmod_mat_entry :: Ptr CFqNModMat -> CLong -> CLong -> IO (Ptr CFqNMod)
- fq_nmod_mat_entry_set :: Ptr CFqNModMat -> CLong -> CLong -> Ptr CFqNMod -> Ptr CFqNModCtx -> IO ()
- fq_nmod_mat_nrows :: Ptr CFqNModMat -> Ptr CFqNModCtx -> IO CLong
- fq_nmod_mat_ncols :: Ptr CFqNModMat -> Ptr CFqNModCtx -> IO CLong
- fq_nmod_mat_swap :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModCtx -> IO ()
- fq_nmod_mat_swap_entrywise :: Ptr CFqNModMat -> Ptr CFqNModMat -> IO ()
- fq_nmod_mat_zero :: Ptr CFqNModMat -> Ptr CFqNModCtx -> IO ()
- fq_nmod_mat_one :: Ptr CFqNModMat -> Ptr CFqNModCtx -> IO ()
- fq_nmod_mat_swap_rows :: Ptr CFqNModMat -> Ptr CLong -> CLong -> CLong -> IO ()
- fq_nmod_mat_swap_cols :: Ptr CFqNModMat -> Ptr CLong -> CLong -> CLong -> IO ()
- fq_nmod_mat_invert_rows :: Ptr CFqNModMat -> Ptr CLong -> IO ()
- fq_nmod_mat_invert_cols :: Ptr CFqNModMat -> Ptr CLong -> IO ()
- fq_nmod_mat_set_nmod_mat :: Ptr CFqNModMat -> Ptr CNModMat -> Ptr CFqNModCtx -> IO ()
- fq_nmod_mat_set_fmpz_mod_mat :: Ptr CFqNModMat -> Ptr CFmpzModMat -> Ptr CFqNModCtx -> IO ()
- fq_nmod_mat_concat_vertical :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModCtx -> IO ()
- fq_nmod_mat_concat_horizontal :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModCtx -> IO ()
- fq_nmod_mat_print_pretty :: Ptr CFqNModMat -> Ptr CFqNModCtx -> IO ()
- fq_nmod_mat_fprint_pretty :: Ptr CFile -> Ptr CFqNModMat -> Ptr CFqNModCtx -> IO CInt
- fq_nmod_mat_print :: Ptr CFqNModMat -> Ptr CFqNModCtx -> IO ()
- fq_nmod_mat_fprint :: Ptr CFile -> Ptr CFqNModMat -> Ptr CFqNModCtx -> IO CInt
- fq_nmod_mat_window_init :: Ptr CFqNModMat -> Ptr CFqNModMat -> CLong -> CLong -> CLong -> CLong -> Ptr CFqNModCtx -> IO ()
- fq_nmod_mat_window_clear :: Ptr CFqNModMat -> Ptr CFqNModCtx -> IO ()
- fq_nmod_mat_randtest :: Ptr CFqNModMat -> Ptr CFRandState -> Ptr CFqNModCtx -> IO ()
- fq_nmod_mat_randpermdiag :: Ptr CFqNModMat -> Ptr CFRandState -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO CInt
- fq_nmod_mat_randrank :: Ptr CFqNModMat -> Ptr CFRandState -> CLong -> Ptr CFqNModCtx -> IO ()
- fq_nmod_mat_randops :: Ptr CFqNModMat -> CLong -> Ptr CFRandState -> Ptr CFqNModCtx -> IO ()
- fq_nmod_mat_randtril :: Ptr CFqNModMat -> Ptr CFRandState -> CInt -> Ptr CFqNModCtx -> IO ()
- fq_nmod_mat_randtriu :: Ptr CFqNModMat -> Ptr CFRandState -> CInt -> Ptr CFqNModCtx -> IO ()
- fq_nmod_mat_equal :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModCtx -> IO CInt
- fq_nmod_mat_is_zero :: Ptr CFqNModMat -> Ptr CFqNModCtx -> IO CInt
- fq_nmod_mat_is_one :: Ptr CFqNModMat -> Ptr CFqNModCtx -> IO CInt
- fq_nmod_mat_is_empty :: Ptr CFqNModMat -> Ptr CFqNModCtx -> IO CInt
- fq_nmod_mat_is_square :: Ptr CFqNModMat -> Ptr CFqNModCtx -> IO CInt
- fq_nmod_mat_add :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModCtx -> IO ()
- fq_nmod_mat_sub :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModCtx -> IO ()
- fq_nmod_mat_neg :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModCtx -> IO ()
- fq_nmod_mat_mul :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModCtx -> IO ()
- fq_nmod_mat_mul_classical :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModCtx -> IO ()
- fq_nmod_mat_mul_KS :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModCtx -> IO ()
- fq_nmod_mat_submul :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModCtx -> IO ()
- fq_nmod_mat_mul_vec :: Ptr (Ptr CFqNMod) -> Ptr CFqNModMat -> Ptr (Ptr CFqNMod) -> CLong -> IO ()
- fq_nmod_mat_mul_vec_ptr :: Ptr (Ptr (Ptr CFqNMod)) -> Ptr CFqNModMat -> Ptr (Ptr (Ptr CFqNMod)) -> CLong -> IO ()
- fq_nmod_mat_vec_mul :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModMat -> IO ()
- fq_nmod_mat_vec_mul_ptr :: Ptr (Ptr (Ptr CFqNMod)) -> Ptr (Ptr (Ptr CFqNMod)) -> CLong -> Ptr CFqNModMat -> IO ()
- fq_nmod_mat_inv :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqCtx -> IO CInt
- fq_nmod_mat_lu :: Ptr CLong -> Ptr CFqNModMat -> CInt -> Ptr CFqNModCtx -> IO CLong
- fq_nmod_mat_lu_classical :: Ptr CLong -> Ptr CFqNModMat -> CInt -> Ptr CFqNModCtx -> IO CLong
- fq_nmod_mat_lu_recursive :: Ptr CLong -> Ptr CFqNModMat -> CInt -> Ptr CFqNModCtx -> IO CLong
- fq_nmod_mat_rref :: Ptr CFqNModMat -> Ptr CFqNModCtx -> IO CLong
- fq_nmod_mat_reduce_row :: Ptr CFqNModMat -> Ptr CLong -> Ptr CLong -> CLong -> Ptr CFqNModCtx -> IO CLong
- fq_nmod_mat_solve_tril :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModMat -> CInt -> Ptr CFqNModCtx -> IO ()
- fq_nmod_mat_solve_tril_classical :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModMat -> CInt -> Ptr CFqNModCtx -> IO ()
- fq_nmod_mat_solve_tril_recursive :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModMat -> CInt -> Ptr CFqNModCtx -> IO ()
- fq_nmod_mat_solve_triu :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModMat -> CInt -> Ptr CFqNModCtx -> IO ()
- fq_nmod_mat_solve_triu_classical :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModMat -> CInt -> Ptr CFqNModCtx -> IO ()
- fq_nmod_mat_solve_triu_recursive :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModMat -> CInt -> Ptr CFqNModCtx -> IO ()
- fq_nmod_mat_solve :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModCtx -> IO CInt
- fq_nmod_mat_can_solve :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModCtx -> IO CInt
- fq_nmod_mat_similarity :: Ptr CFqNModMat -> CLong -> Ptr CFqNMod -> Ptr CFqNModCtx -> IO ()
- fq_nmod_mat_charpoly_danilevsky :: Ptr CFqNModPoly -> Ptr CFqNModMat -> Ptr CFqNModCtx -> IO ()
- fq_nmod_mat_charpoly :: Ptr CFqNModPoly -> Ptr CFqNModMat -> Ptr CFqNModCtx -> IO ()
- fq_nmod_mat_minpoly :: Ptr CFqNModPoly -> Ptr CFqNModMat -> Ptr CFqNModCtx -> IO ()
Matrices over finite fields (word-size characteristic)
data CFqNModMat Source #
Instances
Storable CFqNModMat Source # | |
Defined in Data.Number.Flint.Fq.NMod.Mat.FFI sizeOf :: CFqNModMat -> Int # alignment :: CFqNModMat -> Int # peekElemOff :: Ptr CFqNModMat -> Int -> IO CFqNModMat # pokeElemOff :: Ptr CFqNModMat -> Int -> CFqNModMat -> IO () # peekByteOff :: Ptr b -> Int -> IO CFqNModMat # pokeByteOff :: Ptr b -> Int -> CFqNModMat -> IO () # peek :: Ptr CFqNModMat -> IO CFqNModMat # poke :: Ptr CFqNModMat -> CFqNModMat -> IO () # |
withFqNModMat :: FqNModMat -> (Ptr CFqNModMat -> IO a) -> IO (FqNModMat, a) Source #
Memory management
fq_nmod_mat_init :: Ptr CFqNModMat -> CLong -> CLong -> Ptr CFqNModCtx -> IO () Source #
fq_nmod_mat_init mat rows cols ctx
Initialises mat
to a rows
-by-cols
matrix with coefficients in
\(\mathbf{F}_{q}\) given by ctx
. All elements are set to zero.
fq_nmod_mat_init_set :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModCtx -> IO () Source #
fq_nmod_mat_init_set mat src ctx
Initialises mat
and sets its dimensions and elements to those of
src
.
fq_nmod_mat_clear :: Ptr CFqNModMat -> Ptr CFqNModCtx -> IO () Source #
fq_nmod_mat_clear mat ctx
Clears the matrix and releases any memory it used. The matrix cannot be
used again until it is initialised. This function must be called exactly
once when finished using an fq_nmod_mat_t
object.
fq_nmod_mat_set :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModCtx -> IO () Source #
fq_nmod_mat_set mat src ctx
Sets mat
to a copy of src
. It is assumed that mat
and src
have
identical dimensions.
Basic properties and manipulation
fq_nmod_mat_entry :: Ptr CFqNModMat -> CLong -> CLong -> IO (Ptr CFqNMod) Source #
fq_nmod_mat_entry mat i j
Directly accesses the entry in mat
in row \(i\) and column \(j\),
indexed from zero. No bounds checking is performed.
fq_nmod_mat_entry_set :: Ptr CFqNModMat -> CLong -> CLong -> Ptr CFqNMod -> Ptr CFqNModCtx -> IO () Source #
fq_nmod_mat_entry_set mat i j x ctx
Sets the entry in mat
in row \(i\) and column \(j\) to x
.
fq_nmod_mat_nrows :: Ptr CFqNModMat -> Ptr CFqNModCtx -> IO CLong Source #
fq_nmod_mat_nrows mat ctx
Returns the number of rows in mat
.
fq_nmod_mat_ncols :: Ptr CFqNModMat -> Ptr CFqNModCtx -> IO CLong Source #
fq_nmod_mat_ncols mat ctx
Returns the number of columns in mat
.
fq_nmod_mat_swap :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModCtx -> IO () Source #
fq_nmod_mat_swap mat1 mat2 ctx
Swaps two matrices. The dimensions of mat1
and mat2
are allowed to
be different.
fq_nmod_mat_swap_entrywise :: Ptr CFqNModMat -> Ptr CFqNModMat -> IO () Source #
fq_nmod_mat_swap_entrywise mat1 mat2
Swaps two matrices by swapping the individual entries rather than swapping the contents of the structs.
fq_nmod_mat_zero :: Ptr CFqNModMat -> Ptr CFqNModCtx -> IO () Source #
fq_nmod_mat_zero mat ctx
Sets all entries of mat
to 0.
fq_nmod_mat_one :: Ptr CFqNModMat -> Ptr CFqNModCtx -> IO () Source #
fq_nmod_mat_one mat ctx
Sets all diagonal entries of mat
to 1 and all other entries to 0.
fq_nmod_mat_swap_rows :: Ptr CFqNModMat -> Ptr CLong -> CLong -> CLong -> IO () Source #
fq_nmod_mat_swap_rows mat perm r s
Swaps rows r
and s
of mat
. If perm
is non-NULL
, the
permutation of the rows will also be applied to perm
.
fq_nmod_mat_swap_cols :: Ptr CFqNModMat -> Ptr CLong -> CLong -> CLong -> IO () Source #
fq_nmod_mat_swap_cols mat perm r s
Swaps columns r
and s
of mat
. If perm
is non-NULL
, the
permutation of the columns will also be applied to perm
.
fq_nmod_mat_invert_rows :: Ptr CFqNModMat -> Ptr CLong -> IO () Source #
fq_nmod_mat_invert_rows mat perm
Swaps rows i
and r - i
of mat
for 0 <= i < r/2
, where r
is
the number of rows of mat
. If perm
is non-NULL
, the permutation of
the rows will also be applied to perm
.
fq_nmod_mat_invert_cols :: Ptr CFqNModMat -> Ptr CLong -> IO () Source #
fq_nmod_mat_invert_cols mat perm
Swaps columns i
and c - i
of mat
for 0 <= i < c/2
, where c
is the number of columns of mat
. If perm
is non-NULL
, the
permutation of the columns will also be applied to perm
.
Conversions
fq_nmod_mat_set_nmod_mat :: Ptr CFqNModMat -> Ptr CNModMat -> Ptr CFqNModCtx -> IO () Source #
fq_nmod_mat_set_nmod_mat mat1 mat2 ctx
Sets the matrix mat1
to the matrix mat2
.
fq_nmod_mat_set_fmpz_mod_mat :: Ptr CFqNModMat -> Ptr CFmpzModMat -> Ptr CFqNModCtx -> IO () Source #
fq_nmod_mat_set_fmpz_mod_mat mat1 mat2 ctx
Sets the matrix mat1
to the matrix mat2
.
Concatenate
fq_nmod_mat_concat_vertical :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModCtx -> IO () Source #
fq_nmod_mat_concat_vertical res mat1 mat2 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\).
fq_nmod_mat_concat_horizontal :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModCtx -> IO () Source #
fq_nmod_mat_concat_horizontal res mat1 mat2 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)\).
Printing
fq_nmod_mat_print_pretty :: Ptr CFqNModMat -> Ptr CFqNModCtx -> IO () Source #
fq_nmod_mat_print_pretty mat ctx
Pretty-prints mat
to stdout
. A header is printed followed by the
rows enclosed in brackets.
fq_nmod_mat_fprint_pretty :: Ptr CFile -> Ptr CFqNModMat -> Ptr CFqNModCtx -> IO CInt Source #
fq_nmod_mat_fprint_pretty file mat ctx
Pretty-prints mat
to file
. 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.
fq_nmod_mat_print :: Ptr CFqNModMat -> Ptr CFqNModCtx -> IO () Source #
fq_nmod_mat_print mat ctx
Prints mat
to stdout
. A header is printed followed by the rows
enclosed in brackets.
fq_nmod_mat_fprint :: Ptr CFile -> Ptr CFqNModMat -> Ptr CFqNModCtx -> IO CInt Source #
fq_nmod_mat_fprint file mat ctx
Prints mat
to file
. 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
fq_nmod_mat_window_init :: Ptr CFqNModMat -> Ptr CFqNModMat -> CLong -> CLong -> CLong -> CLong -> Ptr CFqNModCtx -> IO () Source #
fq_nmod_mat_window_init window mat r1 c1 r2 c2 ctx
Initializes the matrix window
to be an r2 - r1
by c2 - c1
submatrix of mat
whose (0,0)
entry is the (r1, c1)
entry of mat
.
The memory for the elements of window
is shared with mat
.
fq_nmod_mat_window_clear :: Ptr CFqNModMat -> Ptr CFqNModCtx -> IO () Source #
fq_nmod_mat_window_clear window ctx
Clears the matrix window
and releases any memory that it uses. Note
that the memory to the underlying matrix that window
points to is not
freed.
Random matrix generation
fq_nmod_mat_randtest :: Ptr CFqNModMat -> Ptr CFRandState -> Ptr CFqNModCtx -> IO () Source #
fq_nmod_mat_randtest mat state ctx
Sets the elements of mat
to random elements of \(\mathbf{F}_{q}\),
given by ctx
.
fq_nmod_mat_randpermdiag :: Ptr CFqNModMat -> Ptr CFRandState -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO CInt Source #
fq_nmod_mat_randpermdiag mat state diag n ctx
Sets mat
to a random permutation of the diagonal matrix with \(n\)
leading entries given by the vector diag
. It is assumed that the main
diagonal of mat
has room for at least \(n\) entries.
Returns \(0\) or \(1\), depending on whether the permutation is even or odd respectively.
fq_nmod_mat_randrank :: Ptr CFqNModMat -> Ptr CFRandState -> CLong -> Ptr CFqNModCtx -> IO () Source #
fq_nmod_mat_randrank mat state rank 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_nmod_mat_randops
.
fq_nmod_mat_randops :: Ptr CFqNModMat -> CLong -> Ptr CFRandState -> Ptr CFqNModCtx -> IO () Source #
fq_nmod_mat_randops mat count state ctx
Randomises mat
by performing elementary row or column operations. More
precisely, at most count
random additions or subtractions of distinct
rows and columns will be performed. This leaves the rank (and for square
matrices, determinant) unchanged.
fq_nmod_mat_randtril :: Ptr CFqNModMat -> Ptr CFRandState -> CInt -> Ptr CFqNModCtx -> IO () Source #
fq_nmod_mat_randtril mat state unit ctx
Sets mat
to a random lower triangular matrix. If unit
is 1, it will
have ones on the main diagonal, otherwise it will have random nonzero
entries on the main diagonal.
fq_nmod_mat_randtriu :: Ptr CFqNModMat -> Ptr CFRandState -> CInt -> Ptr CFqNModCtx -> IO () Source #
fq_nmod_mat_randtriu mat state unit ctx
Sets mat
to a random upper triangular matrix. If unit
is 1, it will
have ones on the main diagonal, otherwise it will have random nonzero
entries on the main diagonal.
Comparison
fq_nmod_mat_equal :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModCtx -> IO CInt Source #
fq_nmod_mat_equal mat1 mat2 ctx
Returns nonzero if mat1 and mat2 have the same dimensions and elements, and zero otherwise.
fq_nmod_mat_is_zero :: Ptr CFqNModMat -> Ptr CFqNModCtx -> IO CInt Source #
fq_nmod_mat_is_zero mat ctx
Returns a non-zero value if all entries mat
are zero, and otherwise
returns zero.
fq_nmod_mat_is_one :: Ptr CFqNModMat -> Ptr CFqNModCtx -> IO CInt Source #
fq_nmod_mat_is_one mat ctx
Returns a non-zero value if all entries mat
are zero except the
diagonal entries which must be one, otherwise returns zero.
fq_nmod_mat_is_empty :: Ptr CFqNModMat -> Ptr CFqNModCtx -> IO CInt Source #
fq_nmod_mat_is_empty mat ctx
Returns a non-zero value if the number of rows or the number of columns
in mat
is zero, and otherwise returns zero.
fq_nmod_mat_is_square :: Ptr CFqNModMat -> Ptr CFqNModCtx -> IO CInt Source #
fq_nmod_mat_is_square mat ctx
Returns a non-zero value if the number of rows is equal to the number of
columns in mat
, and otherwise returns zero.
Addition and subtraction
fq_nmod_mat_add :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModCtx -> IO () Source #
fq_nmod_mat_add C A B ctx
Computes \(C = A + B\). Dimensions must be identical.
fq_nmod_mat_sub :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModCtx -> IO () Source #
fq_nmod_mat_sub C A B ctx
Computes \(C = A - B\). Dimensions must be identical.
fq_nmod_mat_neg :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModCtx -> IO () Source #
fq_nmod_mat_neg A B ctx
Sets \(B = -A\). Dimensions must be identical.
Matrix multiplication
fq_nmod_mat_mul :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModCtx -> IO () Source #
fq_nmod_mat_mul C A B ctx
Sets \(C = AB\). Dimensions must be compatible for matrix multiplication. Aliasing is allowed. This function automatically chooses between classical and KS multiplication.
fq_nmod_mat_mul_classical :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModCtx -> IO () Source #
fq_nmod_mat_mul_classical C A B 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.
fq_nmod_mat_mul_KS :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModCtx -> IO () Source #
fq_nmod_mat_mul_KS C A B ctx
Sets \(C = AB\). Dimensions must be compatible for matrix multiplication. \(C\) is not allowed to be aliased with \(A\) or \(B\). Uses Kronecker substitution to perform the multiplication over the integers.
fq_nmod_mat_submul :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModCtx -> IO () Source #
fq_nmod_mat_submul D C A B ctx
Sets \(D = C + AB\). \(C\) and \(D\) may be aliased with each other but not with \(A\) or \(B\).
fq_nmod_mat_mul_vec :: Ptr (Ptr CFqNMod) -> Ptr CFqNModMat -> Ptr (Ptr CFqNMod) -> CLong -> IO () Source #
fq_nmod_mat_mul_vec c A b blen
fq_nmod_mat_mul_vec_ptr :: Ptr (Ptr (Ptr CFqNMod)) -> Ptr CFqNModMat -> Ptr (Ptr (Ptr CFqNMod)) -> CLong -> IO () Source #
fq_nmod_mat_mul_vec_ptr c A b blen
Compute a matrix-vector product of A
and (b, blen)
and store the
result in c
. The vector (b, blen)
is either truncated or
zero-extended to the number of columns of A
. The number entries
written to c
is always equal to the number of rows of A
.
fq_nmod_mat_vec_mul :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModMat -> IO () Source #
fq_nmod_mat_vec_mul c a alen B
fq_nmod_mat_vec_mul_ptr :: Ptr (Ptr (Ptr CFqNMod)) -> Ptr (Ptr (Ptr CFqNMod)) -> CLong -> Ptr CFqNModMat -> IO () Source #
fq_nmod_mat_vec_mul_ptr c a alen B
Compute a vector-matrix product of (a, alen)
and B
and and store the
result in c
. The vector (a, alen)
is either truncated or
zero-extended to the number of rows of B
. The number entries written
to c
is always equal to the number of columns of B
.
Inverse
fq_nmod_mat_inv :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqCtx -> IO CInt Source #
fq_nmod_mat_inv B A 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.
LU decomposition
fq_nmod_mat_lu :: Ptr CLong -> Ptr CFqNModMat -> CInt -> Ptr CFqNModCtx -> IO CLong Source #
fq_nmod_mat_lu P A rank_check 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_nmod_mat_lu_recursive
.
fq_nmod_mat_lu_classical :: Ptr CLong -> Ptr CFqNModMat -> CInt -> Ptr CFqNModCtx -> IO CLong Source #
fq_nmod_mat_lu_classical P A rank_check 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_nmod_mat_lu
. Uses Gaussian elimination.
fq_nmod_mat_lu_recursive :: Ptr CLong -> Ptr CFqNModMat -> CInt -> Ptr CFqNModCtx -> IO CLong Source #
fq_nmod_mat_lu_recursive P A rank_check 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_nmod_mat_lu
. Uses recursive block
decomposition, switching to classical Gaussian elimination for
sufficiently small blocks.
Reduced row echelon form
fq_nmod_mat_rref :: Ptr CFqNModMat -> Ptr CFqNModCtx -> IO CLong Source #
fq_nmod_mat_rref A 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.
fq_nmod_mat_reduce_row :: Ptr CFqNModMat -> Ptr CLong -> Ptr CLong -> CLong -> Ptr CFqNModCtx -> IO CLong Source #
fq_nmod_mat_reduce_row A P L n 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
fq_nmod_mat_solve_tril :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModMat -> CInt -> Ptr CFqNModCtx -> IO () Source #
fq_nmod_mat_solve_tril X L B unit 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.
fq_nmod_mat_solve_tril_classical :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModMat -> CInt -> Ptr CFqNModCtx -> IO () Source #
fq_nmod_mat_solve_tril_classical X L B unit 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.
fq_nmod_mat_solve_tril_recursive :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModMat -> CInt -> Ptr CFqNModCtx -> IO () Source #
fq_nmod_mat_solve_tril_recursive X L B unit 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{aligned} ` \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} \end{aligned}\]
to reduce the problem to matrix multiplication and triangular solving of smaller systems.
fq_nmod_mat_solve_triu :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModMat -> CInt -> Ptr CFqNModCtx -> IO () Source #
fq_nmod_mat_solve_triu X U B unit 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.
fq_nmod_mat_solve_triu_classical :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModMat -> CInt -> Ptr CFqNModCtx -> IO () Source #
fq_nmod_mat_solve_triu_classical X U B unit 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.
fq_nmod_mat_solve_triu_recursive :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModMat -> CInt -> Ptr CFqNModCtx -> IO () Source #
fq_nmod_mat_solve_triu_recursive X U B unit 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{aligned} ` \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} \end{aligned}\]
to reduce the problem to matrix multiplication and triangular solving of smaller systems.
Solving
fq_nmod_mat_solve :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModCtx -> IO CInt Source #
fq_nmod_mat_solve X A B 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.
fq_nmod_mat_can_solve :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModCtx -> IO CInt Source #
fq_nmod_mat_can_solve X A B ctx
Solves the matrix-matrix equation \(AX = B\) over \(Fq\).
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.
Transforms
fq_nmod_mat_similarity :: Ptr CFqNModMat -> CLong -> Ptr CFqNMod -> Ptr CFqNModCtx -> IO () Source #
fq_nmod_mat_similarity M r d 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.
Characteristic polynomial
fq_nmod_mat_charpoly_danilevsky :: Ptr CFqNModPoly -> Ptr CFqNModMat -> Ptr CFqNModCtx -> IO () Source #
fq_nmod_mat_charpoly_danilevsky p M ctx
Compute the characteristic polynomial \(p\) of the matrix \(M\). The matrix is assumed to be square.
fq_nmod_mat_charpoly :: Ptr CFqNModPoly -> Ptr CFqNModMat -> Ptr CFqNModCtx -> IO () Source #
fq_nmod_mat_charpoly p M ctx
Compute the characteristic polynomial \(p\) of the matrix \(M\). The matrix is required to be square, otherwise an exception is raised.
Minimal polynomial
fq_nmod_mat_minpoly :: Ptr CFqNModPoly -> Ptr CFqNModMat -> Ptr CFqNModCtx -> IO () Source #
fq_nmod_mat_minpoly p M ctx
Compute the minimal polynomial \(p\) of the matrix \(M\). The matrix is required to be square, otherwise an exception is raised.