| Safe Haskell | None |
|---|
Quipper.Algorithms.CL.SmithReduction
Description
This module provides functions for reducing (non-square) matrices towards Smith Normal Form, and hence for computing the structure of finitely-presented Abelian groups.
The SNF transformation is similar to Gaussian elimination, but over integer matrices, (more generally, matrices over any principal ideal domain)
For background on how this is used to compute the structure of Abelian groups, see the MathOverflow question http://mathoverflow.net/questions/12009/, in particular Greg Kuperberg’s answer http://mathoverflow.net/questions/12009#12053.
We do not implement full SNF reduction here, but rather just as much as is needed to compute the structure of finitely presented Abelian groups from matrix presentations.
Synopsis
- data CLMatrix a = CLMatrix Int Int Bool (Array (Int, Int) a)
- transpose :: CLMatrix a -> CLMatrix a
- rows :: CLMatrix a -> Int
- cols :: CLMatrix a -> Int
- row_list :: CLMatrix a -> [Int]
- col_list :: CLMatrix a -> [Int]
- idx :: CLMatrix a -> Int -> Int -> (Int, Int)
- (!!!) :: CLMatrix a -> (Int, Int) -> a
- (///) :: CLMatrix a -> [(Int, Int, a)] -> CLMatrix a
- matrix_from_list :: [[a]] -> CLMatrix a
- delete_row :: Int -> CLMatrix a -> CLMatrix a
- delete_col :: Int -> CLMatrix a -> CLMatrix a
- elim_entry_with_pivot :: Integral int => CLMatrix int -> Int -> Int -> Int -> CLMatrix int
- clean_first_row :: Integral int => CLMatrix int -> CLMatrix int
- clean_first_col :: Integral int => CLMatrix int -> CLMatrix int
- clean_first_row_col :: Integral int => CLMatrix int -> CLMatrix int
- structure_constants_from_matrix :: (Show int, Integral int) => CLMatrix int -> [int]
- group_order_from_matrix :: (Show int, Integral int) => CLMatrix int -> int
Matrix type and basic access functions.
A data type to hold an m×n matrix (Mij),
with entries from an arbitrary type a.
The fields are: integers m and n; a flag t to indicate that a matrix
should be considered formally transposed; and an m×n array M
containing the entries. When t is False, m is the number of rows,
and n the number of columns; when t is True, this is reversed.
(The point of the flag is to allow efficient transposition, and hence to allow operations on rows to be implemented in terms of the corresponding operations on columns without loss of efficiency.)
idx :: CLMatrix a -> Int -> Int -> (Int, Int) Source #
An index tuple for a matrix, at a given row and column
(///) :: CLMatrix a -> [(Int, Int, a)] -> CLMatrix a infixl 9 Source #
Update a matrix by a list of (i,j,m_i_j) pairs (all indexes assumed in range of original matrix).
matrix_from_list :: [[a]] -> CLMatrix a Source #
Construct an CLMatrix from a list such as [[1,0],[4,-5]].
Assumes that all inner lists are the same length, and that the overall list is of length ≥1.
Smith reduction
elim_entry_with_pivot :: Integral int => CLMatrix int -> Int -> Int -> Int -> CLMatrix int Source #
elim_entry_with_pivot M i j j'
clean_first_row :: Integral int => CLMatrix int -> CLMatrix int Source #
Given a matrix, repeatedly use elim_entry_with_pivot to put the
top row into clean form (d,0,…,0).
clean_first_col :: Integral int => CLMatrix int -> CLMatrix int Source #
Dual to clean_first_row.
clean_first_row_col :: Integral int => CLMatrix int -> CLMatrix int Source #
Given a matrix, repeatedly apply clean_first_row and its analogue
on columns until the first row and column are both in clean form.
Structure of Abelian Groups
structure_constants_from_matrix :: (Show int, Integral int) => CLMatrix int -> [int] Source #
Given a matrix, taken as presenting an Abelian group (with generators corresponding to columns of the matrix, and relations specified by the rows), compute the structure constants of the group, not necessarily sorted.
That is, return a list of natural numbers [n0,…,ns] such that the group given by the input presentation is isomorphic to the product of the cyclic groups ℤ/(ni).