Safe Haskell | Safe-Inferred |
---|
- staircase' :: Integral a => SparseMatrix a -> SparseMatrix a -> (SparseMatrix a, SparseMatrix a)
- staircase :: Integral α => SparseMatrix α -> (SparseMatrix α, SparseMatrix α)
- extGCD :: (Num α, Integral α) => α -> α -> (SparseVector α, SparseVector α)
Documentation
staircase' :: Integral a => SparseMatrix a -> SparseMatrix a -> (SparseMatrix a, SparseMatrix a)Source
Staircase Form of matrix.
It takes matrix itself and initial protocol matrix and applies all transformations to both of them in the same way, and then returns matrix in the staircase form and a transformation matrix.
Usage 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.
staircase :: Integral α => SparseMatrix α -> (SparseMatrix α, SparseMatrix α)Source
Staircase Form of matrix.
It uses an identity matrix as initial protocol matrix for staircase'
.
It returns also transformation matrix:
>>>
let (s, t) = staircase m in t × m == s
True
Usage 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.
extGCD :: (Num α, Integral α) => α -> α -> (SparseVector α, SparseVector α)Source
Extended Euclid algorithm
extGCD a b
returns (x,y)
, such that
x · (a <> b) == gcd a b
y · (a <> b) == 0