linbox
1
|
Repository of functions for rank by elimination on sparse matrices. More...
#include <gauss.h>
Public Member Functions | |
GaussDomain (const Field &F) | |
The field parameter is the domain over which to perform computations. | |
const Field & | field () |
template<class Matrix > | |
unsigned long & | InPlaceLinearPivoting (unsigned long &rank, Element &determinant, Matrix &A, unsigned long Ni, unsigned long Nj) |
Sparse in place Gaussian elimination with reordering to reduce fill-in. pivots are chosen in sparsest column of sparsest row. This runs in linear overhead. It is similar in spirit but different from Markovitz' approach. | |
template<class Matrix > | |
unsigned long & | NoReordering (unsigned long &rank, Element &determinant, Matrix &LigneA, unsigned long Ni, unsigned long Nj) |
Sparse Gaussian elimination without reordering. | |
template<class Matrix > | |
unsigned long & | LUin (unsigned long &rank, Matrix &A) |
Dense in place LU factorization without reordering. | |
template<class Matrix > | |
unsigned long & | upperin (unsigned long &rank, Matrix &A) |
Dense in place Gaussian elimination without reordering. | |
rank | |
Callers of the different rank routines\ -/ The "in" suffix indicates in place computation\ -/ Without Ni, Nj, the Matrix parameter must be a vector of sparse row vectors, NOT storing any zero.\ -/ Calls rankinLinearPivoting (by default) or rankinNoReordering | |
template<class Matrix > | |
unsigned long & | rankin (unsigned long &rank, Matrix &A, SparseEliminationTraits::PivotStrategy reord=SparseEliminationTraits::PIVOT_LINEAR) |
template<class Matrix > | |
unsigned long & | rankin (unsigned long &rank, Matrix &A, unsigned long Ni, unsigned long Nj, SparseEliminationTraits::PivotStrategy reord=SparseEliminationTraits::PIVOT_LINEAR) |
template<class Matrix > | |
unsigned long & | rank (unsigned long &rank, const Matrix &A, SparseEliminationTraits::PivotStrategy reord=SparseEliminationTraits::PIVOT_LINEAR) |
template<class Matrix > | |
unsigned long & | rank (unsigned long &rank, const Matrix &A, unsigned long Ni, unsigned long Nj, SparseEliminationTraits::PivotStrategy reord=SparseEliminationTraits::PIVOT_LINEAR) |
det | |
Callers of the different determinant routines\ -/ The "in" suffix indicates in place computation\ -/ Without Ni, Nj, the Matrix parameter must be a vector of sparse row vectors, NOT storing any zero.\ -/ Calls LinearPivoting (by default) or NoReordering | |
template<class Matrix > | |
Element & | detin (Element &determinant, Matrix &A, SparseEliminationTraits::PivotStrategy reord=SparseEliminationTraits::PIVOT_LINEAR) |
template<class Matrix > | |
Element & | detin (Element &determinant, Matrix &A, unsigned long Ni, unsigned long Nj, SparseEliminationTraits::PivotStrategy reord=SparseEliminationTraits::PIVOT_LINEAR) |
template<class Matrix > | |
Element & | det (Element &determinant, const Matrix &A, SparseEliminationTraits::PivotStrategy reord=SparseEliminationTraits::PIVOT_LINEAR) |
template<class Matrix > | |
Element & | det (Element &determinant, const Matrix &A, unsigned long Ni, unsigned long Nj, SparseEliminationTraits::PivotStrategy reord=SparseEliminationTraits::PIVOT_LINEAR) |
Repository of functions for rank by elimination on sparse matrices.
Several versions allow for adjustment of the pivoting strategy and for choosing in-place elimination or for not modifying the input matrix. Also an LU interface is offered.
const Field& field | ( | ) | [inline] |
accessor for the field of computation
unsigned long& InPlaceLinearPivoting | ( | unsigned long & | rank, |
Element & | determinant, | ||
Matrix & | A, | ||
unsigned long | Ni, | ||
unsigned long | Nj | ||
) |
Sparse in place Gaussian elimination with reordering to reduce fill-in. pivots are chosen in sparsest column of sparsest row. This runs in linear overhead. It is similar in spirit but different from Markovitz' approach.
Using : SparseFindPivot(..., density) for sparsest column, and eliminate (..., density)
The Matrix parameter must meet the LinBox sparse matrix interface. [check details]. The computedet indicates whether the algorithm must compute the determionant as it goes
[Jean-Guillaume Dumas and Gilles Villard, Computing the rank of sparse matrices over finite fields. In Ganzha et~al. CASC'2002, pages 47--62.]
unsigned long& NoReordering | ( | unsigned long & | rank, |
Element & | determinant, | ||
Matrix & | LigneA, | ||
unsigned long | Ni, | ||
unsigned long | Nj | ||
) |
Sparse Gaussian elimination without reordering.
Gaussian elimination is done on a copy of the matrix. Using : SparseFindPivot eliminate
Requirements : SLA is an array of sparse rows WARNING : NOT IN PLACE, THERE IS A COPY. Without reordering (Pivot is first non-zero in row)
unsigned long& LUin | ( | unsigned long & | rank, |
Matrix & | A | ||
) |
Dense in place LU factorization without reordering.
Using : FindPivot and LU
unsigned long& upperin | ( | unsigned long & | rank, |
Matrix & | A | ||
) |
Dense in place Gaussian elimination without reordering.
Using : FindPivot and LU