Data.Number.Flint.Fmpz.Mat

An FmpzMat represents an matrix over integer. This module implements operations on matrices over integers.

Basic usage

Create a 3x3 matrix over integers, set it to the unit matrix and print it.

import Data.Number.Flint

main = do
  withNewFmpzMat 3 2 $ \a -> do
    fmpz_mat_one a
    fmpz_mat_print a
    putStr "\n"

Running main yields:

>>> main
3 3  1 0 0 0 1 0 0 0 1

Matrices over the integers

data FmpzMat

Constructors

FmpzMat !(ForeignPtr CFmpzMat)

Instances

Semigroup FmpzMat

Defined in Data.Number.Flint.Fmpz.Mat.Instances

Methods

(<>) :: FmpzMat -> FmpzMat -> FmpzMat

sconcat :: NonEmpty FmpzMat -> FmpzMat

stimes :: Integral b => b -> FmpzMat -> FmpzMat

Num FmpzMat

Defined in Data.Number.Flint.Fmpz.Mat.Instances

Methods

(+) :: FmpzMat -> FmpzMat -> FmpzMat

(-) :: FmpzMat -> FmpzMat -> FmpzMat

(*) :: FmpzMat -> FmpzMat -> FmpzMat

negate :: FmpzMat -> FmpzMat

abs :: FmpzMat -> FmpzMat

signum :: FmpzMat -> FmpzMat

fromInteger :: Integer -> FmpzMat

Show FmpzMat

Defined in Data.Number.Flint.Fmpz.Mat.Instances

Methods

showsPrec :: Int -> FmpzMat -> ShowS

show :: FmpzMat -> String

showList :: [FmpzMat] -> ShowS

Eq FmpzMat

Defined in Data.Number.Flint.Fmpz.Mat.Instances

Methods

(==) :: FmpzMat -> FmpzMat -> Bool

(/=) :: FmpzMat -> FmpzMat -> Bool

data CFmpzMat

Constructors

CFmpzMat (Ptr CFmpz) CLong CLong (Ptr (Ptr CFmpz))

Instances

Storable CFmpzMat

Defined in Data.Number.Flint.Fmpz.Mat.FFI

Methods

sizeOf :: CFmpzMat -> Int

alignment :: CFmpzMat -> Int

peekElemOff :: Ptr CFmpzMat -> Int -> IO CFmpzMat

pokeElemOff :: Ptr CFmpzMat -> Int -> CFmpzMat -> IO ()

peekByteOff :: Ptr b -> Int -> IO CFmpzMat

pokeByteOff :: Ptr b -> Int -> CFmpzMat -> IO ()

peek :: Ptr CFmpzMat -> IO CFmpzMat

poke :: Ptr CFmpzMat -> CFmpzMat -> IO ()

Constructor

newFmpzMat :: CLong -> CLong -> IO FmpzMat

withFmpzMat :: FmpzMat -> (Ptr CFmpzMat -> IO a) -> IO (FmpzMat, a)

withNewFmpzMat :: CLong -> CLong -> (Ptr CFmpzMat -> IO a) -> IO (FmpzMat, a)

Memory management

fmpz_mat_init :: Ptr CFmpzMat -> CLong -> CLong -> IO ()

fmpz_mat_init mat rows cols

Initialises a matrix with the given number of rows and columns for use.

fmpz_mat_clear :: Ptr CFmpzMat -> IO ()

fmpz_mat_clear mat

Clears the given matrix.

Basic assignment and manipulation

fmpz_mat_set :: Ptr CFmpzMat -> Ptr CFmpzMat -> IO ()

fmpz_mat_set mat1 mat2

Sets mat1 to a copy of mat2. The dimensions of mat1 and mat2 must be the same.

fmpz_mat_init_set :: Ptr CFmpzMat -> Ptr CFmpzMat -> IO ()

fmpz_mat_init_set mat src

Initialises the matrix mat to the same size as src and sets it to a copy of src.

fmpz_mat_swap :: Ptr CFmpzMat -> Ptr CFmpzMat -> IO ()

fmpz_mat_swap mat1 mat2

Swaps two matrices. The dimensions of mat1 and mat2 are allowed to be different.

fmpz_mat_swap_entrywise :: Ptr CFmpzMat -> Ptr CFmpzMat -> IO ()

fmpz_mat_swap_entrywise mat1 mat2

Swaps two matrices by swapping the individual entries rather than swapping the contents of the structs.

fmpz_mat_entry :: Ptr CFmpzMat -> CLong -> CLong -> IO (Ptr CFmpz)

fmpz_mat_entry mat i j

Returns a reference to the entry of mat at row \(i\) and column \(j\). This reference can be passed as an input or output variable to any function in the fmpz module for direct manipulation.

Both \(i\) and \(j\) must not exceed the dimensions of the matrix. No bounds checking is performed.

fmpz_mat_set_entry :: Ptr CFmpzMat -> CLong -> CLong -> Ptr CFmpz -> IO ()

fmpz_mat_get_entry :: Ptr CFmpz -> Ptr CFmpzMat -> CLong -> CLong -> IO ()

fmpz_mat_zero :: Ptr CFmpzMat -> IO ()

fmpz_mat_zero mat

Sets all entries of mat to 0.

fmpz_mat_one :: Ptr CFmpzMat -> IO ()

fmpz_mat_one mat

Sets mat to the unit matrix, having ones on the main diagonal and zeroes elsewhere. If mat is nonsquare, it is set to the truncation of a unit matrix.

fmpz_mat_swap_rows :: Ptr CFmpzMat -> Ptr CLong -> CLong -> CLong -> IO ()

fmpz_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.

fmpz_mat_swap_cols :: Ptr CFmpzMat -> Ptr CLong -> CLong -> CLong -> IO ()

fmpz_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.

fmpz_mat_invert_rows :: Ptr CFmpzMat -> Ptr CLong -> IO ()

fmpz_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.

fmpz_mat_invert_cols :: Ptr CFmpzMat -> Ptr CLong -> IO ()

fmpz_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.

Window

fmpz_mat_window_init :: Ptr CFmpzMat -> Ptr CFmpzMat -> CLong -> CLong -> CLong -> CLong -> IO ()

fmpz_mat_window_init window mat r1 c1 r2 c2

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.

fmpz_mat_window_clear :: Ptr CFmpzMat -> IO ()

fmpz_mat_window_clear window

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

fmpz_mat_randbits :: Ptr CFmpzMat -> Ptr CFRandState -> CFBitCnt -> IO ()

fmpz_mat_randbits mat state bits

Sets the entries of mat to random signed integers whose absolute values have the given number of binary bits.

fmpz_mat_randtest :: Ptr CFmpzMat -> Ptr CFRandState -> CFBitCnt -> IO ()

fmpz_mat_randtest mat state bits

Sets the entries of mat to random signed integers whose absolute values have a random number of bits up to the given number of bits inclusive.

fmpz_mat_randintrel :: Ptr CFmpzMat -> Ptr CFRandState -> CFBitCnt -> IO ()

fmpz_mat_randintrel mat state bits

Sets mat to be a random integer relations matrix, with signed entries up to the given number of bits.

The number of columns of mat must be equal to one more than the number of rows. The format of the matrix is a set of random integers in the left hand column and an identity matrix in the remaining square submatrix.

fmpz_mat_randsimdioph :: Ptr CFmpzMat -> Ptr CFRandState -> CFBitCnt -> CFBitCnt -> IO ()

fmpz_mat_randsimdioph mat state bits bits2

Sets mat to a random simultaneous diophantine matrix.

The matrix must be square. The top left entry is set to 2^bits2. The remainder of that row is then set to signed random integers of the given number of binary bits. The remainder of the first column is zero. Running down the rest of the diagonal are the values 2^bits with all remaining entries zero.

fmpz_mat_randntrulike :: Ptr CFmpzMat -> Ptr CFRandState -> CFBitCnt -> CULong -> IO ()

fmpz_mat_randntrulike mat state bits q

Sets a square matrix mat of even dimension to a random NTRU like matrix.

The matrix is broken into four square submatrices. The top left submatrix is set to the identity. The bottom left submatrix is set to the zero matrix. The bottom right submatrix is set to \(q\) times the identity matrix. Finally the top right submatrix has the following format. A random vector \(h\) of length \(r/2\) is created, with random signed entries of the given number of bits. Then entry \((i, j)\) of the submatrix is set to \(h[i + j \bmod{r/2}]\).

fmpz_mat_randntrulike2 :: Ptr CFmpzMat -> Ptr CFRandState -> CFBitCnt -> CULong -> IO ()

fmpz_mat_randntrulike2 mat state bits q

Sets a square matrix mat of even dimension to a random NTRU like matrix.

The matrix is broken into four square submatrices. The top left submatrix is set to \(q\) times the identity matrix. The top right submatrix is set to the zero matrix. The bottom right submatrix is set to the identity matrix. Finally the bottom left submatrix has the following format. A random vector \(h\) of length \(r/2\) is created, with random signed entries of the given number of bits. Then entry \((i, j)\) of the submatrix is set to \(h[i + j \bmod{r/2}]\).

fmpz_mat_randajtai :: Ptr CFmpzMat -> Ptr CFRandState -> CDouble -> IO ()

fmpz_mat_randajtai mat state alpha

Sets a square matrix mat to a random ajtai matrix. The diagonal entries \((i, i)\) are set to a random entry in the range \([1, 2^{b-1}]\) inclusive where \(b = \lfloor(2 r - i)^\alpha\rfloor\) for some double parameter~`alpha`. The entries below the diagonal in column~`i` are set to a random entry in the range \((-2^b + 1, 2^b - 1)\) whilst the entries to the right of the diagonal in row~`i` are set to zero.

fmpz_mat_randpermdiag :: Ptr CFmpzMat -> Ptr CFRandState -> Ptr CFmpz -> CLong -> IO CInt

fmpz_mat_randpermdiag mat state diag n

Sets mat to a random permutation of the rows and columns of a given diagonal matrix. The diagonal matrix is specified in the form of an array of the \(n\) initial entries on the main diagonal.

The return value is \(0\) or \(1\) depending on whether the permutation is even or odd.

fmpz_mat_randrank :: Ptr CFmpzMat -> Ptr CFRandState -> CLong -> CFBitCnt -> IO ()

fmpz_mat_randrank mat state rank bits

Sets mat to a random sparse matrix with the given rank, having exactly as many non-zero elements as the rank, with the nonzero elements being random integers of the given bit size.

The matrix can be transformed into a dense matrix with unchanged rank by subsequently calling fmpz_mat_randops.

fmpz_mat_randdet :: Ptr CFmpzMat -> Ptr CFRandState -> Ptr CFmpz -> IO ()

fmpz_mat_randdet mat state det

Sets mat to a random sparse matrix with minimal number of nonzero entries such that its determinant has the given value.

Note that the matrix will be zero if det is zero. In order to generate a non-zero singular matrix, the function fmpz_mat_randrank can be used.

The matrix can be transformed into a dense matrix with unchanged determinant by subsequently calling fmpz_mat_randops.

fmpz_mat_randops :: Ptr CFmpzMat -> Ptr CFRandState -> CLong -> IO ()

fmpz_mat_randops mat state count

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, the determinant) unchanged.

Input and output

fmpz_mat_get_str :: Ptr CFmpzMat -> IO CString

fmpz_mat_get_str_pretty :: Ptr CFmpzMat -> IO CString

fmpz_mat_fprint :: Ptr CFile -> Ptr CFmpzMat -> IO CInt

fmpz_mat_fprint file mat

Prints the given matrix to the stream file. The format is the number of rows, a space, the number of columns, two spaces, then a space separated list of coefficients, one row after the other.

In case of success, returns a positive value; otherwise, returns a non-positive value.

fmpz_mat_fprint_pretty :: Ptr CFile -> Ptr CFmpzMat -> IO CInt

fmpz_mat_fprint_pretty file mat

Prints the given matrix to the stream file. 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.

In case of success, returns a positive value; otherwise, returns a non-positive value.

fmpz_mat_print :: Ptr CFmpzMat -> IO CInt

fmpz_mat_print mat

Prints the given matrix to the stream stdout. For further details, see fmpz_mat_fprint.

fmpz_mat_print_pretty :: Ptr CFmpzMat -> IO CInt

fmpz_mat_print_pretty mat

Prints the given matrix to stdout. For further details, see fmpz_mat_fprint_pretty.

fmpz_mat_fread :: Ptr CFile -> Ptr CFmpzMat -> IO CInt

fmpz_mat_fread file mat

Reads a matrix from the stream file, storing the result in mat. The expected format is the number of rows, a space, the number of columns, two spaces, then a space separated list of coefficients, one row after the other.

In case of success, returns a positive number. In case of failure, returns a non-positive value.

fmpz_mat_read :: Ptr CFmpzMat -> IO CInt

fmpz_mat_read mat

Reads a matrix from stdin, storing the result in mat.

In case of success, returns a positive number. In case of failure, returns a non-positive value.

Comparison

fmpz_mat_equal :: Ptr CFmpzMat -> Ptr CFmpzMat -> IO CInt

fmpz_mat_equal mat1 mat2

Returns a non-zero value if mat1 and mat2 have the same dimensions and entries, and zero otherwise.

fmpz_mat_is_zero :: Ptr CFmpzMat -> IO CInt

fmpz_mat_is_zero mat

Returns a non-zero value if all entries mat are zero, and otherwise returns zero.

fmpz_mat_is_one :: Ptr CFmpzMat -> IO CInt

fmpz_mat_is_one mat

Returns a non-zero value if mat is the unit matrix or the truncation of a unit matrix, and otherwise returns zero.

fmpz_mat_is_empty :: Ptr CFmpzMat -> IO CInt

fmpz_mat_is_empty mat

Returns a non-zero value if the number of rows or the number of columns in mat is zero, and otherwise returns zero.

fmpz_mat_is_square :: Ptr CFmpzMat -> IO CInt

fmpz_mat_is_square mat

Returns a non-zero value if the number of rows is equal to the number of columns in mat, and otherwise returns zero.

fmpz_mat_is_zero_row :: Ptr CFmpzMat -> CLong -> IO CInt

fmpz_mat_is_zero_row mat i

Returns a non-zero value if row \(i\) of mat is zero.

Transpose

fmpz_mat_transpose :: Ptr CFmpzMat -> Ptr CFmpzMat -> IO ()

fmpz_mat_transpose B A

Sets \(B\) to \(A^T\), the transpose of \(A\). Dimensions must be compatible. \(A\) and \(B\) are allowed to be the same object if \(A\) is a square matrix.

Concatenate

fmpz_mat_concat_vertical :: Ptr CFmpzMat -> Ptr CFmpzMat -> Ptr CFmpzMat -> IO ()

fmpz_mat_concat_vertical res mat1 mat2

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\).

fmpz_mat_concat_horizontal :: Ptr CFmpzMat -> Ptr CFmpzMat -> Ptr CFmpzMat -> IO ()

fmpz_mat_concat_horizontal res mat1 mat2

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)\).

Modular reduction and reconstruction

fmpz_mat_get_nmod_mat :: Ptr CNModMat -> Ptr CFmpzMat -> IO ()

fmpz_mat_get_nmod_mat Amod A

Sets the entries of Amod to the entries of A reduced by the modulus of Amod.

fmpz_mat_set_nmod_mat :: Ptr CFmpzMat -> Ptr CNModMat -> IO ()

fmpz_mat_set_nmod_mat A Amod

Sets the entries of Amod to the residues in Amod, normalised to the interval \(-m/2 <= r < m/2\) where \(m\) is the modulus.

fmpz_mat_set_nmod_mat_unsigned :: Ptr CFmpzMat -> Ptr CNModMat -> IO ()

fmpz_mat_set_nmod_mat_unsigned A Amod

Sets the entries of Amod to the residues in Amod, normalised to the interval \(0 <= r < m\) where \(m\) is the modulus.

fmpz_mat_CRT_ui :: Ptr CFmpzMat -> Ptr CFmpzMat -> Ptr CFmpz -> Ptr CNModMat -> CInt -> IO ()

fmpz_mat_CRT_ui res mat1 m1 mat2 sign

Given mat1 with entries modulo m and mat2 with modulus \(n\), sets res to the CRT reconstruction modulo \(mn\) with entries satisfying \(-mn/2 <= c < mn/2\) (if sign = 1) or \(0 <= c < mn\) (if sign = 0).

fmpz_mat_multi_mod_ui_precomp :: Ptr CNModMat -> CLong -> Ptr CFmpzMat -> Ptr CFmpzComb -> Ptr CFmpzCombTemp -> IO ()

fmpz_mat_multi_mod_ui_precomp residues nres mat comb temp

Sets each of the nres matrices in residues to mat reduced modulo the modulus of the respective matrix, given precomputed comb and comb_temp structures.

fmpz_mat_multi_mod_ui :: Ptr CNModMat -> CLong -> Ptr CFmpzMat -> IO ()

fmpz_mat_multi_mod_ui residues nres mat

Sets each of the nres matrices in residues to mat reduced modulo the modulus of the respective matrix.

This function is provided for convenience purposes. For reducing or reconstructing multiple integer matrices over the same set of moduli, it is faster to use\ fmpz_mat_multi_mod_precomp.

fmpz_mat_multi_CRT_ui_precomp :: Ptr CFmpzMat -> Ptr CNModMat -> CLong -> Ptr CFmpzComb -> Ptr CFmpzCombTemp -> CInt -> IO ()

fmpz_mat_multi_CRT_ui_precomp mat residues nres comb temp sign

Reconstructs mat from its images modulo the nres matrices in residues, given precomputed comb and comb_temp structures.

fmpz_mat_multi_CRT_ui :: Ptr CFmpzMat -> Ptr CNModMat -> CLong -> CInt -> IO ()

fmpz_mat_multi_CRT_ui mat residues nres sign

Reconstructs mat from its images modulo the nres matrices in residues.

This function is provided for convenience purposes. For reducing or reconstructing multiple integer matrices over the same set of moduli, it is faster to use fmpz_mat_multi_CRT_ui_precomp.

Addition and subtraction

fmpz_mat_add :: Ptr CFmpzMat -> Ptr CFmpzMat -> Ptr CFmpzMat -> IO ()

fmpz_mat_add C A B

Sets C to the elementwise sum \(A + B\). All inputs must be of the same size. Aliasing is allowed.

fmpz_mat_sub :: Ptr CFmpzMat -> Ptr CFmpzMat -> Ptr CFmpzMat -> IO ()

fmpz_mat_sub C A B

Sets C to the elementwise difference \(A - B\). All inputs must be of the same size. Aliasing is allowed.

fmpz_mat_neg :: Ptr CFmpzMat -> Ptr CFmpzMat -> IO ()

fmpz_mat_neg B A

Sets B to the elementwise negation of A. Both inputs must be of the same size. Aliasing is allowed.

Matrix-scalar arithmetic

fmpz_mat_scalar_mul_si :: Ptr CFmpzMat -> Ptr CFmpzMat -> CLong -> IO ()

fmpz_mat_scalar_mul_si B A c

Set B = A*c where A is an fmpz_mat_t and c is a scalar respectively of type slong, ulong, or fmpz_t. The dimensions of A and B must be compatible.

fmpz_mat_scalar_addmul_si :: Ptr CFmpzMat -> Ptr CFmpzMat -> CLong -> IO ()

fmpz_mat_scalar_addmul_si B A c

Set B = B + A*c where A is an fmpz_mat_t and c is a scalar respectively of type slong, ulong, or fmpz_t. The dimensions of A and B must be compatible.

fmpz_mat_scalar_submul_si :: Ptr CFmpzMat -> Ptr CFmpzMat -> CLong -> IO ()

fmpz_mat_scalar_submul_si B A c

Set B = B - A*c where A is an fmpz_mat_t and c is a scalar respectively of type slong, ulong, or fmpz_t. The dimensions of A and B must be compatible.

fmpz_mat_scalar_addmul_nmod_mat_ui :: Ptr CFmpzMat -> Ptr CNModMat -> CULong -> IO ()

fmpz_mat_scalar_addmul_nmod_mat_ui B A c

Set B = B + A*c where A is an nmod_mat_t and c is a scalar respectively of type ulong or fmpz_t. The dimensions of A and B must be compatible.

fmpz_mat_scalar_divexact_si :: Ptr CFmpzMat -> Ptr CFmpzMat -> CLong -> IO ()

fmpz_mat_scalar_divexact_si B A c

Set A = B / c, where B is an fmpz_mat_t and c is a scalar respectively of type slong, ulong, or fmpz_t, which is assumed to divide all elements of B exactly.

fmpz_mat_scalar_mul_2exp :: Ptr CFmpzMat -> Ptr CFmpzMat -> CULong -> IO ()

fmpz_mat_scalar_mul_2exp B A exp

Set the matrix B to the matrix A, of the same dimensions, multiplied by \(2^{exp}\).

fmpz_mat_scalar_tdiv_q_2exp :: Ptr CFmpzMat -> Ptr CFmpzMat -> CULong -> IO ()

fmpz_mat_scalar_tdiv_q_2exp B A exp

Set the matrix B to the matrix A, of the same dimensions, divided by \(2^{exp}\), rounding down towards zero.

fmpz_mat_scalar_smod :: Ptr CFmpzMat -> Ptr CFmpzMat -> Ptr CFmpz -> IO ()

fmpz_mat_scalar_smod B A P

Set the matrix B to the matrix A, of the same dimensions, with each entry reduced modulo \(P\) in the symmetric moduli system. We require \(P > 0\).

Matrix multiplication

fmpz_mat_mul :: Ptr CFmpzMat -> Ptr CFmpzMat -> Ptr CFmpzMat -> IO ()

fmpz_mat_mul C A B

Sets C to the matrix product \(C = A B\). The matrices must have compatible dimensions for matrix multiplication. Aliasing is allowed.

This function automatically switches between classical and multimodular multiplication, based on a heuristic comparison of the dimensions and entry sizes.

fmpz_mat_mul_classical :: Ptr CFmpzMat -> Ptr CFmpzMat -> Ptr CFmpzMat -> IO ()

fmpz_mat_mul_classical C A B

Sets C to the matrix product \(C = A B\) computed using classical matrix algorithm.

The matrices must have compatible dimensions for matrix multiplication. No aliasing is allowed.

fmpz_mat_mul_strassen :: Ptr CFmpzMat -> Ptr CFmpzMat -> Ptr CFmpzMat -> IO ()

fmpz_mat_mul_strassen C A B

Sets \(C = AB\). Dimensions must be compatible for matrix multiplication. \(C\) is not allowed to be aliased with \(A\) or \(B\). Uses Strassen multiplication (the Strassen-Winograd variant).

_fmpz_mat_mul_multi_mod :: Ptr CFmpzMat -> Ptr CFmpzMat -> Ptr CFmpzMat -> CInt -> CFBitCnt -> IO ()

_fmpz_mat_mul_multi_mod C A B sign bits

Sets C to the matrix product \(C = AB\) computed using a multimodular algorithm. \(C\) is computed modulo several small prime numbers and reconstructed using the Chinese Remainder Theorem. This generally becomes more efficient than classical multiplication for large matrices.

The absolute value of the elements of \(C\) should be \(< 2^{\text{bits}}\), and sign should be \(0\) if the entries of \(C\) are known to be nonnegative and \(1\) otherwise. The function fmpz_mat_mul_multi_mod calculates a rigorous bound automatically. If the default bound is too pessimistic, _fmpz_mat_mul_multi_mod can be used with a custom bound.

The matrices must have compatible dimensions for matrix multiplication. No aliasing is allowed.

fmpz_mat_mul_blas :: Ptr CFmpzMat -> Ptr CFmpzMat -> Ptr CFmpzMat -> IO CInt

fmpz_mat_mul_blas C A B

Tries to set \(C = AB\) using BLAS and returns \(1\) for success and \(0\) for failure. Dimensions must be compatible for matrix multiplication. No aliasing is allowed. This function currently will fail if the matrices are empty, their dimensions are too large, or their max bits size is over one million bits.

fmpz_mat_mul_fft :: Ptr CFmpzMat -> Ptr CFmpzMat -> Ptr CFmpzMat -> IO ()

fmpz_mat_mul_fft C A B

Aliasing is allowed.

fmpz_mat_sqr :: Ptr CFmpzMat -> Ptr CFmpzMat -> IO ()

fmpz_mat_sqr B A

Sets B to the square of the matrix A, which must be a square matrix. Aliasing is allowed. The function calls fmpz_mat_mul for dimensions less than 12 and calls fmpz_mat_sqr_bodrato for cases in which the latter is faster.

fmpz_mat_sqr_bodrato :: Ptr CFmpzMat -> Ptr CFmpzMat -> IO ()

fmpz_mat_sqr_bodrato B A

Sets B to the square of the matrix A, which must be a square matrix. Aliasing is allowed. The bodrato algorithm is described in [Bodrato2010]. It is highly efficient for squaring matrices which satisfy both the following conditions : (a) large elements (b) dimensions less than 150.

fmpz_mat_pow :: Ptr CFmpzMat -> Ptr CFmpzMat -> CULong -> IO ()

fmpz_mat_pow B A e

Sets B to the matrix A raised to the power e, where A must be a square matrix. Aliasing is allowed.

_fmpz_mat_mul_small :: Ptr CFmpzMat -> Ptr CFmpzMat -> Ptr CFmpzMat -> IO CInt

_fmpz_mat_mul_small C A B

This internal function sets \(C\) to the matrix product \(C = A B\) computed using classical matrix algorithm assuming that all entries of \(A\) and \(B\) are small, that is, have bits \( \le FLINT\_BITS - 2\). No aliasing is allowed.

_fmpz_mat_mul_double_word :: Ptr CFmpzMat -> Ptr CFmpzMat -> Ptr CFmpzMat -> IO ()

_fmpz_mat_mul_double_word C A B

This function is only for internal use and assumes that either:

- the entries of \(A\) and \(B\) are all nonnegative and strictly less than \(2^{2*FLINT_BITS}\), or - the entries of \(A\) and \(B\) are all strictly less than \(2^{2*FLINT_BITS - 1}\) in absolute value.

fmpz_mat_mul_fmpz_vec :: Ptr CFmpz -> Ptr CFmpzMat -> Ptr CFmpz -> CLong -> IO ()

fmpz_mat_mul_fmpz_vec 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.

fmpz_mat_fmpz_vec_mul :: Ptr CFmpz -> Ptr CFmpz -> CLong -> Ptr CFmpzMat -> IO ()

fmpz_mat_fmpz_vec_mul 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

fmpz_mat_inv :: Ptr CFmpzMat -> Ptr CFmpz -> Ptr CFmpzMat -> IO CInt

fmpz_mat_inv Ainv den A

Sets (Ainv, den) to the inverse matrix of A. Returns 1 if A is nonsingular and 0 if A is singular. Aliasing of Ainv and A is allowed.

The denominator is not guaranteed to be minimal, but is guaranteed to be a divisor of the determinant of A.

This function uses a direct formula for matrices of size two or less, and otherwise solves for the identity matrix using fraction-free LU decomposition.

Kronecker product

fmpz_mat_kronecker_product :: Ptr CFmpzMat -> Ptr CFmpzMat -> Ptr CFmpzMat -> IO ()

fmpz_mat_kronecker_product C A B

Sets C to the Kronecker product of A and B.

Content

fmpz_mat_content :: Ptr CFmpz -> Ptr CFmpzMat -> IO ()

fmpz_mat_content mat_gcd A

Sets mat_gcd as the gcd of all the elements of the matrix A. Returns 0 if the matrix is empty.

Trace

fmpz_mat_trace :: Ptr CFmpz -> Ptr CFmpzMat -> IO ()

fmpz_mat_trace trace mat

Computes the trace of the matrix, i.e. the sum of the entries on the main diagonal. The matrix is required to be square.

Determinant

fmpz_mat_det :: Ptr CFmpz -> Ptr CFmpzMat -> IO ()

fmpz_mat_det det A

Sets det to the determinant of the square matrix \(A\). The matrix of dimension \(0 \times 0\) is defined to have determinant 1.

This function automatically chooses between fmpz_mat_det_cofactor, fmpz_mat_det_bareiss, fmpz_mat_det_modular and fmpz_mat_det_modular_accelerated (with proved = 1), depending on the size of the matrix and its entries.

fmpz_mat_det_cofactor :: Ptr CFmpz -> Ptr CFmpzMat -> IO ()

fmpz_mat_det_cofactor det A

Sets det to the determinant of the square matrix \(A\) computed using direct cofactor expansion. This function only supports matrices up to size \(4 \times 4\).

fmpz_mat_det_bareiss :: Ptr CFmpz -> Ptr CFmpzMat -> IO ()

fmpz_mat_det_bareiss det A

Sets det to the determinant of the square matrix \(A\) computed using the Bareiss algorithm. A copy of the input matrix is row reduced using fraction-free Gaussian elimination, and the determinant is read off from the last element on the main diagonal.

fmpz_mat_det_modular :: Ptr CFmpz -> Ptr CFmpzMat -> CInt -> IO ()

fmpz_mat_det_modular det A proved

Sets det to the determinant of the square matrix \(A\) (if proved = 1), or a probabilistic value for the determinant (proved = 0), computed using a multimodular algorithm.

The determinant is computed modulo several small primes and reconstructed using the Chinese Remainder Theorem. With proved = 1, sufficiently many primes are chosen to satisfy the bound computed by fmpz_mat_det_bound. With proved = 0, the determinant is considered determined if it remains unchanged modulo several consecutive primes (currently if their product exceeds \(2^{100}\)).

fmpz_mat_det_modular_accelerated :: Ptr CFmpz -> Ptr CFmpzMat -> CInt -> IO ()

fmpz_mat_det_modular_accelerated det A proved

Sets det to the determinant of the square matrix \(A\) (if proved = 1), or a probabilistic value for the determinant (proved = 0), computed using a multimodular algorithm.

This function uses the same basic algorithm as fmpz_mat_det_modular, but instead of computing \(\det(A)\) directly, it generates a divisor \(d\) of \(\det(A)\) and then computes \(x = \det(A) / d\) modulo several small primes not dividing \(d\). This typically accelerates the computation by requiring fewer primes for large matrices, since \(d\) with high probability will be nearly as large as the determinant. This trick is described in [AbbottBronsteinMulders1999].

fmpz_mat_det_modular_given_divisor :: Ptr CFmpz -> Ptr CFmpzMat -> Ptr CFmpz -> CInt -> IO ()

fmpz_mat_det_modular_given_divisor det A d proved

Given a positive divisor \(d\) of \(\det(A)\), sets det to the determinant of the square matrix \(A\) (if proved = 1), or a probabilistic value for the determinant (proved = 0), computed using a multimodular algorithm.

fmpz_mat_det_bound :: Ptr CFmpz -> Ptr CFmpzMat -> IO ()

fmpz_mat_det_bound bound A

Sets bound to a nonnegative integer \(B\) such that \(|\det(A)| \le B\). Assumes \(A\) to be a square matrix. The bound is computed from the Hadamard inequality \(|\det(A)| \le \prod \|a_i\|_2\) where the product is taken over the rows \(a_i\) of \(A\).

fmpz_mat_det_bound_nonzero :: Ptr CFmpz -> Ptr CFmpzMat -> IO ()

fmpz_mat_det_divisor :: Ptr CFmpz -> Ptr CFmpzMat -> IO ()

fmpz_mat_det_divisor d A

Sets \(d\) to some positive divisor of the determinant of the given square matrix \(A\), if the determinant is nonzero. If \(|\det(A)| = 0\), \(d\) will always be set to zero.

A divisor is obtained by solving \(Ax = b\) for an arbitrarily chosen right-hand side \(b\) using Dixon's algorithm and computing the least common multiple of the denominators in \(x\). This yields a divisor \(d\) such that \(|\det(A)| / d\) is tiny with very high probability.

Transforms

fmpz_mat_similarity :: Ptr CFmpzMat -> CLong -> Ptr CFmpz -> IO ()

fmpz_mat_similarity A r d

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.

Characteristic polynomial

_fmpz_mat_charpoly_berkowitz :: Ptr CFmpz -> Ptr CFmpzMat -> IO ()

_fmpz_mat_charpoly_berkowitz cp mat

Sets (cp, n+1) to the characteristic polynomial of an \(n \times n\) square matrix.

fmpz_mat_charpoly_berkowitz :: Ptr CFmpzPoly -> Ptr CFmpzMat -> IO ()

fmpz_mat_charpoly_berkowitz cp mat

Computes the characteristic polynomial of length \(n + 1\) of an \(n \times n\) square matrix. Uses an \(O(n^4)\) algorithm based on the method of Berkowitz.

_fmpz_mat_charpoly_modular :: Ptr CFmpz -> Ptr CFmpzMat -> IO ()

_fmpz_mat_charpoly_modular cp mat

Sets (cp, n+1) to the characteristic polynomial of an \(n \times n\) square matrix.

fmpz_mat_charpoly_modular :: Ptr CFmpzPoly -> Ptr CFmpzMat -> IO ()

fmpz_mat_charpoly_modular cp mat

Computes the characteristic polynomial of length \(n + 1\) of an \(n \times n\) square matrix. Uses a modular method based on an \(O(n^3)\) method over \(\mathbb{Z}/n\mathbb{Z}\).

_fmpz_mat_charpoly :: Ptr CFmpz -> Ptr CFmpzMat -> IO ()

_fmpz_mat_charpoly cp mat

Sets (cp, n+1) to the characteristic polynomial of an \(n \times n\) square matrix.

fmpz_mat_charpoly :: Ptr CFmpzPoly -> Ptr CFmpzMat -> IO ()

fmpz_mat_charpoly cp mat

Computes the characteristic polynomial of length \(n + 1\) of an \(n \times n\) square matrix.

Minimal polynomial

_fmpz_mat_minpoly_modular :: Ptr CFmpz -> Ptr CFmpzMat -> IO CLong

_fmpz_mat_minpoly_modular cp mat

Sets (cp, n+1) to the modular polynomial of an \(n \times n\) square matrix and returns its length.

fmpz_mat_minpoly_modular :: Ptr CFmpzPoly -> Ptr CFmpzMat -> IO ()

fmpz_mat_minpoly_modular cp mat

Computes the minimal polynomial of an \(n \times n\) square matrix. Uses a modular method based on an average time \(O~(n^3)\), worst case \(O(n^4)\) method over \(\mathbb{Z}/n\mathbb{Z}\).

_fmpz_mat_minpoly :: Ptr CFmpz -> Ptr CFmpzMat -> IO CLong

_fmpz_mat_minpoly cp mat

Sets cp to the minimal polynomial of an \(n \times n\) square matrix and returns its length.

fmpz_mat_minpoly :: Ptr CFmpzPoly -> Ptr CFmpzMat -> IO ()

fmpz_mat_minpoly cp mat

Computes the minimal polynomial of an \(n \times n\) square matrix.

Rank

fmpz_mat_rank :: Ptr CFmpzMat -> IO CLong

fmpz_mat_rank A

Returns the rank, that is, the number of linearly independent columns (equivalently, rows), of \(A\). The rank is computed by row reducing a copy of \(A\).

Column partitioning

fmpz_mat_col_partition :: Ptr CLong -> Ptr CFmpzMat -> CInt -> IO CInt

fmpz_mat_col_partition part M short_circuit

Returns the number \(p\) of distinct columns of \(M\) (or \(0\) if the flag short_circuit is set and this number is greater than the number of rows of \(M\)). The entries of array part are set to values in \([0, p)\) such that two entries of part are equal iff the corresponding columns of \(M\) are equal. This function is used in van Hoeij polynomial factoring.

Nonsingular solving

fmpz_mat_solve :: Ptr CFmpzMat -> Ptr CFmpz -> Ptr CFmpzMat -> Ptr CFmpzMat -> IO CInt

fmpz_mat_solve X den A B

Solves the equation \(AX = B\) for nonsingular \(A\). More precisely, computes (X, den) such that \(AX = B \times \operatorname{den}\). Returns 1 if \(A\) is nonsingular and 0 if \(A\) is singular. The computed denominator will not generally be minimal.

This function uses Cramer's rule for small systems and fraction-free LU decomposition followed by fraction-free forward and back substitution for larger systems.

Note that for very large systems, it is faster to compute a modular solution using fmpz_mat_solve_dixon.

fmpz_mat_solve_fflu :: Ptr CFmpzMat -> Ptr CFmpz -> Ptr CFmpzMat -> Ptr CFmpzMat -> IO CInt

fmpz_mat_solve_fflu X den A B

Solves the equation \(AX = B\) for nonsingular \(A\). More precisely, computes (X, den) such that \(AX = B \times \operatorname{den}\). Returns 1 if \(A\) is nonsingular and 0 if \(A\) is singular. The computed denominator will not generally be minimal.

Uses fraction-free LU decomposition followed by fraction-free forward and back substitution.

fmpz_mat_solve_fflu_precomp :: Ptr CFmpzMat -> Ptr CLong -> Ptr CFmpzMat -> Ptr CFmpzMat -> IO CInt

fmpz_mat_solve_fflu_precomp X perm FFLU B

Performs fraction-free forward and back substitution given a precomputed fraction-free LU decomposition and corresponding permutation. If no impossible division is encountered, the function returns \(1\). This does not mean the system has a solution, however a return value of \(0\) can only occur if the system is insoluble.

If the return value is \(1\) and \(r\) is the rank of the matrix \(A\) whose FFLU we have, then the first \(r\) rows of \(p(A)y = p(b)d\) hold, where \(d\) is the denominator of the FFLU. The remaining rows must be checked by the caller.

fmpz_mat_solve_cramer :: Ptr CFmpzMat -> Ptr CFmpz -> Ptr CFmpzMat -> Ptr CFmpzMat -> IO CInt

fmpz_mat_solve_cramer X den A B

Solves the equation \(AX = B\) for nonsingular \(A\). More precisely, computes (X, den) such that \(AX = B \times \operatorname{den}\). Returns 1 if \(A\) is nonsingular and 0 if \(A\) is singular.

Uses Cramer's rule. Only systems of size up to \(3 \times 3\) are allowed.

fmpz_mat_solve_bound :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpzMat -> Ptr CFmpzMat -> IO ()

fmpz_mat_solve_bound N D A B

Assuming that \(A\) is nonsingular, computes integers \(N\) and \(D\) such that the reduced numerators and denominators \(n/d\) in \(A^{-1} B\) satisfy the bounds \(0 \le |n| \le N\) and \(0 \le d \le D\).

fmpz_mat_solve_dixon :: Ptr CFmpzMat -> Ptr CFmpz -> Ptr CFmpzMat -> Ptr CFmpzMat -> IO CInt

fmpz_mat_solve_dixon X M A B

Solves \(AX = B\) given a nonsingular square matrix \(A\) and a matrix \(B\) of compatible dimensions, using a modular algorithm. In particular, Dixon's p-adic lifting algorithm is used (currently a non-adaptive version). This is generally the preferred method for large dimensions.

More precisely, this function computes an integer \(M\) and an integer matrix \(X\) such that \(AX = B \bmod M\) and such that all the reduced numerators and denominators of the elements \(x = p/q\) in the full solution satisfy \(2|p|q < M\). As such, the explicit rational solution matrix can be recovered uniquely by passing the output of this function to fmpq_mat_set_fmpz_mat_mod.

A nonzero value is returned if \(A\) is nonsingular. If \(A\) is singular, zero is returned and the values of the output variables will be undefined.

Aliasing between input and output matrices is allowed.

fmpz_mat_solve_dixon_den :: Ptr CFmpzMat -> Ptr CFmpz -> Ptr CFmpzMat -> Ptr CFmpzMat -> IO CInt

fmpz_mat_solve_dixon_den X den A B

Solves the equation \(AX = B\) for nonsingular \(A\). More precisely, computes (X, den) such that \(AX = B \times \operatorname{den}\). Returns 1 if \(A\) is nonsingular and 0 if \(A\) is singular. The computed denominator will not generally be minimal.

Uses the Dixon lifting algorithm with early termination once the lifting stabilises.

fmpz_mat_solve_multi_mod_den :: Ptr CFmpzMat -> Ptr CFmpz -> Ptr CFmpzMat -> Ptr CFmpzMat -> IO CInt

fmpz_mat_solve_multi_mod_den X den A B

Solves the equation \(AX = B\) for nonsingular \(A\). More precisely, computes (X, den) such that \(AX = B \times \operatorname{den}\). Returns 1 if \(A\) is nonsingular and 0 if \(A\) is singular. The computed denominator will not generally be minimal.

Uses a Chinese remainder algorithm with early termination once the lifting stabilises.

fmpz_mat_can_solve_multi_mod_den :: Ptr CFmpzMat -> Ptr CFmpz -> Ptr CFmpzMat -> Ptr CFmpzMat -> IO CInt

fmpz_mat_can_solve_multi_mod_den X den A B

Returns \(1\) if the system \(AX = B\) can be solved. If so it computes (X, den) such that \(AX = B \times \operatorname{den}\). The computed denominator will not generally be minimal.

Uses a Chinese remainder algorithm.

Note that the matrices \(A\) and \(B\) may have any shape as long as they have the same number of rows.

fmpz_mat_can_solve_fflu :: Ptr CFmpzMat -> Ptr CFmpz -> Ptr CFmpzMat -> Ptr CFmpzMat -> IO ()

fmpz_mat_can_solve_fflu X den A B

Returns \(1\) if the system \(AX = B\) can be solved. If so it computes (X, den) such that \(AX = B \times \operatorname{den}\). The computed denominator will not generally be minimal.

Uses a fraction free LU decomposition algorithm.

Note that the matrices \(A\) and \(B\) may have any shape as long as they have the same number of rows.

fmpz_mat_can_solve :: Ptr CFmpzMat -> Ptr CFmpz -> Ptr CFmpzMat -> Ptr CFmpzMat -> IO CInt

fmpz_mat_can_solve X den A B

Returns \(1\) if the system \(AX = B\) can be solved. If so it computes (X, den) such that \(AX = B \times \operatorname{den}\). The computed denominator will not generally be minimal.

Note that the matrices \(A\) and \(B\) may have any shape as long as they have the same number of rows.

Row reduction

fmpz_mat_find_pivot_any :: Ptr CFmpzMat -> CLong -> CLong -> CLong -> IO CLong

fmpz_mat_find_pivot_any mat start_row end_row c

Attempts to find a pivot entry for row reduction. Returns a row index \(r\) between start_row (inclusive) and stop_row (exclusive) such that column \(c\) in mat has a nonzero entry on row \(r\), or returns -1 if no such entry exists.

This implementation simply chooses the first nonzero entry from it encounters. This is likely to be a nearly optimal choice if all entries in the matrix have roughly the same size, but can lead to unnecessary coefficient growth if the entries vary in size.

fmpz_mat_fflu :: Ptr CFmpzMat -> Ptr CFmpz -> Ptr CLong -> Ptr CFmpzMat -> CInt -> IO CLong

fmpz_mat_fflu B den perm A rank_check

Uses fraction-free Gaussian elimination to set (B, den) to a fraction-free LU decomposition of A and returns the rank of A. Aliasing of A and B is allowed.

Pivot elements are chosen with fmpz_mat_find_pivot_any. If perm is non-NULL, the permutation of rows in the matrix will also be applied to perm.

If rank_check is set, the function aborts and returns 0 if the matrix is detected not to have full rank without completing the elimination.

The denominator den is set to \(\pm \operatorname{det}(S)\) where \(S\) is an appropriate submatrix of \(A\) (S = A if \(A\) is square) and the sign is decided by the parity of the permutation. Note that the determinant is not generally the minimal denominator.

The fraction-free LU decomposition is defined in [NakTurWil1997].

fmpz_mat_rref :: Ptr CFmpzMat -> Ptr CFmpz -> Ptr CFmpzMat -> IO CLong

fmpz_mat_rref B den A

Sets (B, den) to the reduced row echelon form of A and returns the rank of A. Aliasing of A and B is allowed.

The algorithm used chooses between fmpz_mat_rref_fflu and fmpz_mat_rref_mul based on the dimensions of the input matrix.

fmpz_mat_rref_fflu :: Ptr CFmpzMat -> Ptr CFmpz -> Ptr CFmpzMat -> IO CLong

fmpz_mat_rref_fflu B den A

Sets (B, den) to the reduced row echelon form of A and returns the rank of A. Aliasing of A and B is allowed.

The algorithm proceeds by first computing a row echelon form using fmpz_mat_fflu. Letting the upper part of this matrix be \((U | V) P\) where \(U\) is full rank upper triangular and \(P\) is a permutation matrix, we obtain the rref by setting \(V\) to \(U^{-1} V\) using back substitution. Scaling each completed row in the back substitution to the denominator den, we avoid introducing new fractions. This strategy is equivalent to the fraction-free Gauss-Jordan elimination in [NakTurWil1997], but faster since only the part \(V\) corresponding to the null space has to be updated.

The denominator den is set to \(\pm \operatorname{det}(S)\) where \(S\) is an appropriate submatrix of \(A\) (S = A if \(A\) is square). Note that the determinant is not generally the minimal denominator.

fmpz_mat_rref_mul :: Ptr CFmpzMat -> Ptr CFmpz -> Ptr CFmpzMat -> IO CLong

fmpz_mat_rref_mul B den A

Sets (B, den) to the reduced row echelon form of A and returns the rank of A. Aliasing of A and B is allowed.

The algorithm works by computing the reduced row echelon form of A modulo a prime \(p\) using nmod_mat_rref. The pivot columns and rows of this matrix will then define a non-singular submatrix of A, nonsingular solving and matrix multiplication can then be used to determine the reduced row echelon form of the whole of A. This procedure is described in [Stein2007].

fmpz_mat_is_in_rref_with_rank :: Ptr CFmpzMat -> Ptr CFmpz -> CLong -> IO CInt

fmpz_mat_is_in_rref_with_rank A den rank

Checks that the matrix \(A/den\) is in reduced row echelon form of rank rank, returns 1 if so and 0 otherwise.

Modular gaussian elimination

fmpz_mat_rref_mod :: Ptr CLong -> Ptr CFmpzMat -> Ptr CFmpz -> IO CLong

fmpz_mat_rref_mod perm A p

Uses fraction-free Gauss-Jordan elimination to set A to its reduced row echelon form and returns the rank of A. All computations are done modulo p.

Pivot elements are chosen with fmpz_mat_find_pivot_any. If perm is non-NULL, the permutation of rows in the matrix will also be applied to perm.

Strong echelon form and Howell form

fmpz_mat_strong_echelon_form_mod :: Ptr CFmpzMat -> Ptr CFmpz -> IO ()

fmpz_mat_strong_echelon_form_mod A mod

Transforms \(A\) such that \(A\) modulo mod is the strong echelon form of the input matrix modulo mod. 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.

\(A\) must have at least as many rows as columns.

fmpz_mat_howell_form_mod :: Ptr CNModMat -> Ptr CFmpz -> IO CLong

fmpz_mat_howell_form_mod A mod

Transforms \(A\) such that \(A\) modulo mod is the Howell form of the input matrix modulo mod. For a definition of the Howell form see [StoMul1998]. The Howell form is computed by first putting \(A\) into strong echelon form and then ordering the rows.

\(A\) must have at least as many rows as columns.

Nullspace

fmpz_mat_nullspace :: Ptr CFmpzMat -> Ptr CFmpzMat -> IO CLong

fmpz_mat_nullspace B A

Computes a basis for the right rational nullspace of \(A\) and returns the dimension of the nullspace (or nullity). \(B\) is set to a matrix with linearly independent columns and maximal rank such that \(AB = 0\) (i.e. \(Ab = 0\) for each column \(b\) in \(B\)), and the rank of \(B\) is returned.

In general, the entries in \(B\) will not be minimal: in particular, the pivot entries in \(B\) will generally differ from unity. \(B\) must be allocated with sufficient space to represent the result (at most \(n \times n\) where \(n\) is the number of column of \(A\)).

Hermite normal form

fmpz_mat_hnf :: Ptr CFmpzMat -> Ptr CFmpzMat -> IO ()

fmpz_mat_hnf H A

Computes an integer matrix H such that H is the unique (row) Hermite normal form of A. The algorithm used is selected from the implementations in FLINT to be the one most likely to be optimal, based on the characteristics of the input matrix.

Aliasing of H and A is allowed. The size of H must be the same as that of A.

fmpz_mat_hnf_transform :: Ptr CFmpzMat -> Ptr CFmpzMat -> Ptr CFmpzMat -> IO ()

fmpz_mat_hnf_transform H U A

Computes an integer matrix H such that H is the unique (row) Hermite normal form of A along with the transformation matrix U such that \(UA = H\). The algorithm used is selected from the implementations in FLINT as per fmpz_mat_hnf.

Aliasing of H and A is allowed. The size of H must be the same as that of A and U must be square of compatible dimension (having the same number of rows as A).

fmpz_mat_hnf_classical :: Ptr CFmpzMat -> Ptr CFmpzMat -> IO ()

fmpz_mat_hnf_classical H A

Computes an integer matrix H such that H is the unique (row) Hermite normal form of A. The algorithm used is straightforward and is described, for example, in [Algorithm 2.4.4] [Coh1996].

Aliasing of H and A is allowed. The size of H must be the same as that of A.

fmpz_mat_hnf_xgcd :: Ptr CFmpzMat -> Ptr CFmpzMat -> IO ()

fmpz_mat_hnf_xgcd H A

Computes an integer matrix H such that H is the unique (row) Hermite normal form of A. The algorithm used is an improvement on the basic algorithm and uses extended gcds to speed up computation, this method is described, for example, in [Algorithm 2.4.5] [Coh1996].

Aliasing of H and A is allowed. The size of H must be the same as that of A.

fmpz_mat_hnf_modular :: Ptr CFmpzMat -> Ptr CFmpzMat -> Ptr CFmpz -> IO ()

fmpz_mat_hnf_modular H A D

Computes an integer matrix H such that H is the unique (row) Hermite normal form of the \(m\times n\) matrix A, where A is assumed to be of rank \(n\) and D is known to be a positive multiple of the determinant of the non-zero rows of H. The algorithm used here is due to Domich, Kannan and Trotter [DomKanTro1987] and is also described in [Algorithm 2.4.8] [Coh1996].

Aliasing of H and A is allowed. The size of H must be the same as that of A.

fmpz_mat_hnf_modular_eldiv :: Ptr CFmpzMat -> Ptr CFmpz -> IO ()

fmpz_mat_hnf_modular_eldiv A D

Transforms the \(m\times n\) matrix A into Hermite normal form, where A is assumed to be of rank \(n\) and D is known to be a positive multiple of the largest elementary divisor of A. The algorithm used here is described in [FieHof2014].

fmpz_mat_hnf_minors :: Ptr CFmpzMat -> Ptr CFmpzMat -> IO ()

fmpz_mat_hnf_minors H A

Computes an integer matrix H such that H is the unique (row) Hermite normal form of the \(m\times n\) matrix A, where A is assumed to be of rank \(n\). The algorithm used here is due to Kannan and Bachem [KanBac1979] and takes the principal minors to Hermite normal form in turn.

Aliasing of H and A is allowed. The size of H must be the same as that of A.

fmpz_mat_hnf_pernet_stein :: Ptr CFmpzMat -> Ptr CFmpzMat -> Ptr CFRandState -> IO ()

fmpz_mat_hnf_pernet_stein H A state

Computes an integer matrix H such that H is the unique (row) Hermite normal form of the \(m\times n\) matrix A. The algorithm used here is due to Pernet and Stein [PernetStein2010].

Aliasing of H and A is allowed. The size of H must be the same as that of A.

fmpz_mat_is_in_hnf :: Ptr CFmpzMat -> IO CInt

fmpz_mat_is_in_hnf A

Checks that the given matrix is in Hermite normal form, returns 1 if so and 0 otherwise.

Smith normal form

fmpz_mat_snf :: Ptr CFmpzMat -> Ptr CFmpzMat -> IO ()

fmpz_mat_snf S A

Computes an integer matrix S such that S is the unique Smith normal form of A. The algorithm used is selected from the implementations in FLINT to be the one most likely to be optimal, based on the characteristics of the input matrix.

Aliasing of S and A is allowed. The size of S must be the same as that of A.

fmpz_mat_snf_diagonal :: Ptr CFmpzMat -> Ptr CFmpzMat -> IO ()

fmpz_mat_snf_diagonal S A

Computes an integer matrix S such that S is the unique Smith normal form of the diagonal matrix A. The algorithm used simply takes gcds of pairs on the diagonal in turn until the Smith form is obtained.

Aliasing of S and A is allowed. The size of S must be the same as that of A.

fmpz_mat_snf_kannan_bachem :: Ptr CFmpzMat -> Ptr CFmpzMat -> IO ()

fmpz_mat_snf_kannan_bachem S A

Computes an integer matrix S such that S is the unique Smith normal form of the diagonal matrix A. The algorithm used here is due to Kannan and Bachem [KanBac1979]

Aliasing of S and A is allowed. The size of S must be the same as that of A.

fmpz_mat_snf_iliopoulos :: Ptr CFmpzMat -> Ptr CFmpzMat -> Ptr CFmpz -> IO ()

fmpz_mat_snf_iliopoulos S A mod

Computes an integer matrix S such that S is the unique Smith normal form of the nonsingular \(n\times n\) matrix A. The algorithm used is due to Iliopoulos [Iliopoulos1989].

Aliasing of S and A is allowed. The size of S must be the same as that of A.

fmpz_mat_is_in_snf :: Ptr CFmpzMat -> IO CInt

fmpz_mat_is_in_snf A

Checks that the given matrix is in Smith normal form, returns 1 if so and 0 otherwise.

Special matrices

fmpz_mat_gram :: Ptr CFmpzMat -> Ptr CFmpzMat -> IO ()

fmpz_mat_gram B A

Sets B to the Gram matrix of the \(m\)-dimensional lattice L in \(n\)-dimensional Euclidean space \(R^n\) spanned by the rows of the \(m \times n\) matrix A. Dimensions must be compatible. A and B are allowed to be the same object if A is a square matrix.

fmpz_mat_is_hadamard :: Ptr CFmpzMat -> IO CInt

fmpz_mat_is_hadamard H

Returns nonzero iff \(H\) is a Hadamard matrix, meaning that it is a square matrix, only has entries that are \(\pm 1\), and satisfies \(H^T = n H^{-1}\) where \(n\) is the matrix size.

fmpz_mat_hadamard :: Ptr CFmpzMat -> IO CInt

fmpz_mat_hadamard H

Attempts to set the matrix \(H\) to a Hadamard matrix, returning 1 if successful and 0 if unsuccessful.

A Hadamard matrix of size \(n\) can only exist if \(n\) is 1, 2, or a multiple of 4. It is not known whether a Hadamard matrix exists for every size that is a multiple of 4. This function uses the Paley construction, which succeeds for all \(n\) of the form \(n = 2^e\) or \(n = 2^e (q + 1)\) where \(q\) is an odd prime power. Orders \(n\) for which Hadamard matrices are known to exist but for which this construction fails are 92, 116, 156, ... (OEIS A046116).

Conversions

fmpz_mat_get_d_mat :: Ptr CDMat -> Ptr CFmpzMat -> IO CInt

fmpz_mat_get_d_mat B A

Sets the entries of B as doubles corresponding to the entries of A, rounding down towards zero if the latter cannot be represented exactly. The return value is -1 if any entry of A is too large to fit in the normal range of a double, and 0 otherwise.

fmpz_mat_get_d_mat_transpose :: Ptr CDMat -> Ptr CFmpzMat -> IO CInt

fmpz_mat_get_d_mat_transpose B A

Sets the entries of B as doubles corresponding to the entries of the transpose of A, rounding down towards zero if the latter cannot be represented exactly. The return value is -1 if any entry of A is too large to fit in the normal range of a double, and 0 otherwise.

Cholesky Decomposition

fmpz_mat_chol_d :: Ptr CDMat -> Ptr CFmpzMat -> IO ()

fmpz_mat_chol_d R A

Computes R, the Cholesky factor of a symmetric, positive definite matrix A using the Cholesky decomposition process. (Sets R such that \(A = RR^{T}\) where R is a lower triangular matrix.)

LLL

fmpz_mat_is_reduced :: Ptr CFmpzMat -> CDouble -> CDouble -> IO CInt

fmpz_mat_is_reduced A delta eta

Returns a non-zero value if the basis A is LLL-reduced with factor (delta, eta), and otherwise returns zero. The second version assumes A is the Gram matrix of the basis.

fmpz_mat_is_reduced_with_removal :: Ptr CFmpzMat -> CDouble -> CDouble -> Ptr CFmpz -> CInt -> IO CInt

fmpz_mat_is_reduced_with_removal A delta eta gs_B newd

Returns a non-zero value if the basis A is LLL-reduced with factor (delta, eta) for each of the first newd vectors and the squared Gram-Schmidt length of each of the remaining \(i\)-th vectors (where \(i \ge\) newd) is greater than gs_B, and otherwise returns zero. The second version assumes A is the Gram matrix of the basis.

Classical LLL

fmpz_mat_lll_original :: Ptr CFmpzMat -> Ptr CFmpq -> Ptr CFmpq -> IO ()

fmpz_mat_lll_original A delta eta

Takes a basis \(x_1, x_2, \ldots, x_m\) of the lattice \(L \subset R^n\) (as the rows of a \(m \times n\) matrix A). The output is an (delta, eta)-reduced basis \(y_1, y_2, \ldots, y_m\) of the lattice \(L\) (as the rows of the same \(m \times n\) matrix A).

Modified LLL

fmpz_mat_lll_storjohann :: Ptr CFmpzMat -> Ptr CFmpq -> Ptr CFmpq -> IO ()

fmpz_mat_lll_storjohann A delta eta

Takes a basis \(x_1, x_2, \ldots, x_m\) of the lattice \(L \subset R^n\) (as the rows of a \(m \times n\) matrix A). The output is an (delta, eta)-reduced basis \(y_1, y_2, \ldots, y_m\) of the lattice \(L\) (as the rows of the same \(m \times n\) matrix A). Uses a modified version of LLL, which has better complexity in terms of the lattice dimension, introduced by Storjohann.

See "Faster Algorithms for Integer Lattice Basis Reduction." Technical Report 249. Zurich, Switzerland: Department Informatik, ETH. July 30, 1996.