Data.Number.Flint.Groups.Bool.Mat

A BoolMat represents a dense matrix over the boolean semiring \(\left<\{0,1\},\vee,\wedge\right>\), implemented as an array of entries of type CInt.

The dimension (number of rows and columns) of a matrix is fixed at initialization, and the user must ensure that inputs and outputs to an operation have compatible dimensions. The number of rows or columns in a matrix can be zero.

Example

import Control.Monad

import Data.Number.Flint

main = do
  a <- newBoolMat 3 5
  withBoolMat a $ \a -> do
    forM_ [0..2] $ \j -> do
      bool_mat_set_entry a j j 1
      bool_mat_set_entry a j (j+2) 1
  print a

Running main yields:

>>> main
[1, 0, 1, 0, 0]
[0, 1, 0, 1, 0]
[0, 0, 1, 0, 1]

Matrices over booleans

data BoolMat

Constructors

BoolMat !(ForeignPtr CBoolMat)

Instances

Show BoolMat

Defined in Data.Number.Flint.Groups.Bool.Mat.Instances

Methods

showsPrec :: Int -> BoolMat -> ShowS

show :: BoolMat -> String

showList :: [BoolMat] -> ShowS

data CBoolMat

Constructors

CBoolMat (Ptr CInt) CLong CLong (Ptr (Ptr CInt))

Instances

Storable CBoolMat

Defined in Data.Number.Flint.Groups.Bool.Mat.FFI

Methods

sizeOf :: CBoolMat -> Int

alignment :: CBoolMat -> Int

peekElemOff :: Ptr CBoolMat -> Int -> IO CBoolMat

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

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

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

peek :: Ptr CBoolMat -> IO CBoolMat

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

newBoolMat :: CLong -> CLong -> IO BoolMat

withBoolMat :: BoolMat -> (Ptr CBoolMat -> IO a) -> IO (BoolMat, a)

withNewBoolMat :: CLong -> CLong -> (Ptr CBoolMat -> IO a) -> IO (BoolMat, a)

Entries

bool_mat_get_entry :: Ptr CBoolMat -> CLong -> CLong -> IO CInt

bool_mat_get_entry mat i j

Returns the entry of matrix mat at row i and column j. foreign import ccall "bool_mat.h bool_mat_get_entry"

bool_mat_set_entry :: Ptr CBoolMat -> CLong -> CLong -> CInt -> IO ()

bool_mat_set_entry mat i j x

Sets the entry of matrix mat at row i and column j to x.

Memory management

bool_mat_init :: Ptr CBoolMat -> CLong -> CLong -> IO ()

bool_mat_init mat r c

Initializes the matrix, setting it to the zero matrix with r rows and c columns.

bool_mat_clear :: Ptr CBoolMat -> IO ()

bool_mat_clear mat

Clears the matrix, deallocating all entries.

bool_mat_is_empty :: Ptr CBoolMat -> IO CInt

bool_mat_is_empty mat

Returns nonzero iff the number of rows or the number of columns in mat is zero. Note that this does not depend on the entry values of mat.

bool_mat_is_square :: Ptr CBoolMat -> IO CInt

bool_mat_is_square mat

Returns nonzero iff the number of rows is equal to the number of columns in mat.

Conversions

bool_mat_entry :: Ptr CBoolMat -> CLong -> CLong -> IO (Ptr CInt)

bool_mat_set :: Ptr CBoolMat -> Ptr CBoolMat -> IO ()

bool_mat_set dest src

Sets dest to src. The operands must have identical dimensions.

Input and output

bool_mat_get_str :: Ptr CBoolMat -> IO CString

bool_mat_print :: Ptr CBoolMat -> IO ()

bool_mat_print mat

Prints each entry in the matrix.

bool_mat_fprint :: Ptr CFile -> Ptr CBoolMat -> IO ()

bool_mat_fprint file mat

Prints each entry in the matrix to the stream file.

Value comparisons

bool_mat_equal :: Ptr CBoolMat -> Ptr CBoolMat -> IO CInt

bool_mat_equal mat1 mat2

Returns nonzero iff the matrices have the same dimensions and identical entries.

bool_mat_any :: Ptr CBoolMat -> IO CInt

bool_mat_any mat

Returns nonzero iff mat has a nonzero entry.

bool_mat_all :: Ptr CBoolMat -> IO CInt

bool_mat_all mat

Returns nonzero iff all entries of mat are nonzero.

bool_mat_is_diagonal :: Ptr CBoolMat -> IO CInt

bool_mat_is_diagonal A

Returns nonzero iff \(i \ne j \implies \bar{A_{ij}}\).

bool_mat_is_lower_triangular :: Ptr CBoolMat -> IO CInt

bool_mat_is_lower_triangular A

Returns nonzero iff \(i < j \implies \bar{A_{ij}}\).

bool_mat_is_transitive :: Ptr CBoolMat -> IO CInt

bool_mat_is_transitive mat

Returns nonzero iff \(A_{ij} \wedge A_{jk} \implies A_{ik}\).

bool_mat_is_nilpotent :: Ptr CBoolMat -> IO CInt

bool_mat_is_nilpotent A

Returns nonzero iff some positive matrix power of \(A\) is zero.

Random generation

bool_mat_randtest :: Ptr CBoolMat -> Ptr CFRandState -> IO ()

bool_mat_randtest mat state

Sets mat to a random matrix.

bool_mat_randtest_diagonal :: Ptr CBoolMat -> Ptr CFRandState -> IO ()

bool_mat_randtest_diagonal mat state

Sets mat to a random diagonal matrix.

bool_mat_randtest_nilpotent :: Ptr CBoolMat -> Ptr CFRandState -> IO ()

bool_mat_randtest_nilpotent mat state

Sets mat to a random nilpotent matrix.

Special matrices

bool_mat_zero :: Ptr CBoolMat -> IO ()

bool_mat_zero mat

Sets all entries in mat to zero.

bool_mat_one :: Ptr CBoolMat -> IO ()

bool_mat_one mat

Sets the entries on the main diagonal to ones, and all other entries to zero.

bool_mat_directed_path :: Ptr CBoolMat -> IO ()

bool_mat_directed_path A

Sets \(A_{ij}\) to \(j = i + 1\). Requires that \(A\) is a square matrix.

bool_mat_directed_cycle :: Ptr CBoolMat -> IO ()

bool_mat_directed_cycle A

Sets \(A_{ij}\) to \(j = (i + 1) \mod n\) where \(n\) is the order of the square matrix \(A\).

Transpose

bool_mat_transpose :: Ptr CBoolMat -> Ptr CBoolMat -> IO ()

bool_mat_transpose dest src

Sets dest to the transpose of src. The operands must have compatible dimensions. Aliasing is allowed.

Arithmetic

bool_mat_complement :: Ptr CBoolMat -> Ptr CBoolMat -> IO ()

bool_mat_complement B A

Sets B to the logical complement of A. That is \(B_{ij}\) is set to \(\bar{A_{ij}}\). The operands must have the same dimensions.

bool_mat_add :: Ptr CBoolMat -> Ptr CBoolMat -> Ptr CBoolMat -> IO ()

bool_mat_add res mat1 mat2

Sets res to the sum of mat1 and mat2. The operands must have the same dimensions.

bool_mat_mul :: Ptr CBoolMat -> Ptr CBoolMat -> Ptr CBoolMat -> IO ()

bool_mat_mul res mat1 mat2

Sets res to the matrix product of mat1 and mat2. The operands must have compatible dimensions for matrix multiplication.

bool_mat_mul_entrywise :: Ptr CBoolMat -> Ptr CBoolMat -> Ptr CBoolMat -> IO ()

bool_mat_mul_entrywise res mat1 mat2

Sets res to the entrywise product of mat1 and mat2. The operands must have the same dimensions.

bool_mat_sqr :: Ptr CBoolMat -> Ptr CBoolMat -> IO ()

bool_mat_sqr B A

Sets B to the matrix square of A. The operands must both be square with the same dimensions.

bool_mat_pow_ui :: Ptr CBoolMat -> Ptr CBoolMat -> CULong -> IO ()

bool_mat_pow_ui B A exp

Sets B to A raised to the power exp. Requires that A is a square matrix.

Special functions

bool_mat_trace :: Ptr CBoolMat -> IO CInt

bool_mat_trace mat

Returns the trace of the matrix, i.e. the sum of entries on the main diagonal of mat. The matrix is required to be square. The sum is in the boolean semiring, so this function returns nonzero iff any entry on the diagonal of mat is nonzero.

bool_mat_nilpotency_degree :: Ptr CBoolMat -> IO CLong

bool_mat_nilpotency_degree A

Returns the nilpotency degree of the \(n \times n\) matrix A. It returns the smallest positive \(k\) such that \(A^k = 0\). If no such \(k\) exists then the function returns \(-1\) if \(n\) is positive, and otherwise it returns \(0\).

bool_mat_transitive_closure :: Ptr CBoolMat -> Ptr CBoolMat -> IO ()

bool_mat_transitive_closure B A

Sets B to the transitive closure \(\sum_{k=1}^\infty A^k\). The matrix A is required to be square.

bool_mat_get_strongly_connected_components :: Ptr CLong -> Ptr CBoolMat -> IO CLong

bool_mat_get_strongly_connected_components p A

Partitions the \(n\) row and column indices of the \(n \times n\) matrix A according to the strongly connected components (SCC) of the graph for which A is the adjacency matrix. If the graph has \(k\) SCCs then the function returns \(k\), and for each vertex \(i \in [0, n-1]\), \(p_i\) is set to the index of the SCC to which the vertex belongs. The SCCs themselves can be considered as nodes in a directed acyclic graph (DAG), and the SCCs are indexed in postorder with respect to that DAG.

bool_mat_all_pairs_longest_walk :: Ptr CFmpzMat -> Ptr CBoolMat -> IO CLong

bool_mat_all_pairs_longest_walk B A

Sets \(B_{ij}\) to the length of the longest walk with endpoint vertices \(i\) and \(j\) in the graph whose adjacency matrix is A. The matrix A must be square. Empty walks with zero length which begin and end at the same vertex are allowed. If \(j\) is not reachable from \(i\) then no walk from \(i\) to \(j\) exists and \(B_{ij}\) is set to the special value \(-1\). If arbitrarily long walks from \(i\) to \(j\) exist then \(B_{ij}\) is set to the special value \(-2\).

The function returns \(-2\) if any entry of \(B_{ij}\) is \(-2\), and otherwise it returns the maximum entry in \(B\), except if \(A\) is empty in which case \(-1\) is returned. Note that the returned value is one less than that of nilpotency_degree.

This function can help quantify entrywise errors in a truncated evaluation of a matrix power series. If A is an indicator matrix with the same sparsity pattern as a matrix \(M\) over the real or complex numbers, and if \(B_{ij}\) does not take the special value \(-2\), then the tail \(\left[ \sum_{k=N}^\infty a_k M^k \right]_{ij}\) vanishes when \(N > B_{ij}\).