Math.LinearAlgebra.Sparse.Algorithms.Staircase

Documentation

staircase :: (Num α, Integral α) => SparseMatrix α -> SparseMatrix α

Staircase Form of matrix. Using of divMod causes Integral context. (TODO: eliminate it) Method: Gauss method applied to the rows of matrix. Though α may be not a field, we repeat the remainder division to obtain zeroes down in the column.

clearColumn :: (Num α, Integral α) => SparseMatrix α -> SparseMatrix α

clearColumn m --> m' From the start, length(m) > 1. m'(1,1) = gcd(firstColumn(m)), m'(i,1)==0 for i>1. m'(1,1) = 0 means that column was zero.

extGCD :: (Num α, Integral α) => α -> α -> (α, SparseMatrix α)

extGCD a b --> (gcd(a,b), tt) a,b are divided repeatedly with remainder, like in extended gcd method. tt is a protocol 2x2 matrix so, [a,b] ·× tt = [gcd(a,b),0]