Repository of functions for rank modulo a prime power by elimination on sparse matrices. More...
#include <smith-form-sparseelim-local.h>
Inheritance diagram for PowerGaussDomain< _Field >:
Public Member Functions | |
| PowerGaussDomain (const Field &F) | |
| The field parameter is the domain over which to perform computations. | |
| template<class Modulo, class Modulo2, class Modulo3> | |
| Modulo & | MY_Zpz_inv_classic (Modulo &u1, const Modulo2 a, const Modulo3 _p) const |
| const Field & | field () const |
| accessor for the field of computation | |
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 (by default) or rankinNoReordering | |
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 (by default) or NoReordering | |
| template<class _Matrix> | |
| Element & | detInPlace (Element &determinant, _Matrix &A, PivotStrategy reord=PivotStrategy::Linear) const |
| Sparse in place Gaussian elimination with reordering to reduce fill-in. | |
| template<class _Matrix> | |
| Element & | detInPlace (Element &determinant, _Matrix &A, size_t Ni, size_t Nj, PivotStrategy reord=PivotStrategy::Linear) const |
| Sparse in place Gaussian elimination with reordering to reduce fill-in. | |
| template<class _Matrix> | |
| Element & | det (Element &determinant, const _Matrix &A, PivotStrategy reord=PivotStrategy::Linear) const |
| Sparse in place Gaussian elimination with reordering to reduce fill-in. | |
| template<class _Matrix> | |
| Element & | det (Element &determinant, const _Matrix &A, size_t Ni, size_t Nj, PivotStrategy reord=PivotStrategy::Linear) const |
| Sparse in place Gaussian elimination with reordering to reduce fill-in. | |
| template<class _Matrix, class Perm> | |
| size_t & | QLUPin (size_t &rank, Element &determinant, Perm &Q, _Matrix &L, _Matrix &U, Perm &P, size_t Ni, size_t Nj) const |
| Sparse in place Gaussian elimination with reordering to reduce fill-in. | |
| template<class _Matrix, class Perm> | |
| size_t & | DenseQLUPin (size_t &rank, Element &determinant, std::deque< std::pair< size_t, size_t > > &invQ, _Matrix &L, _Matrix &U, Perm &P, size_t Ni, size_t Nj) const |
| Sparse in place Gaussian elimination with reordering to reduce fill-in. | |
| template<class _Matrix, class Perm, class Vector1, class Vector2> | |
| Vector1 & | solve (Vector1 &x, Vector1 &w, size_t rank, const Perm &Q, const _Matrix &L, const _Matrix &U, const Perm &P, const Vector2 &b) const |
| Sparse in place Gaussian elimination with reordering to reduce fill-in. | |
| template<class _Matrix, class Vector1, class Vector2> | |
| Vector1 & | solveInPlace (Vector1 &x, _Matrix &A, const Vector2 &b) const |
| Sparse in place Gaussian elimination with reordering to reduce fill-in. | |
| template<class _Matrix, class Vector1, class Vector2, class Random> | |
| Vector1 & | solveInPlace (Vector1 &x, _Matrix &A, const Vector2 &b, Random &generator) const |
| Sparse in place Gaussian elimination with reordering to reduce fill-in. | |
| template<class _Matrix, class Perm, class Block> | |
| Block & | nullspacebasis (Block &x, size_t rank, const _Matrix &U, const Perm &P) const |
| Sparse in place Gaussian elimination with reordering to reduce fill-in. | |
| template<class _Matrix, class Block> | |
| Block & | nullspacebasis (Block &x, const _Matrix &A) const |
| Sparse in place Gaussian elimination with reordering to reduce fill-in. | |
| template<class _Matrix, class Block> | |
| Block & | nullspacebasisin (Block &x, _Matrix &A) const |
| Sparse in place Gaussian elimination with reordering to reduce fill-in. | |
| template<class _Matrix> | |
| size_t & | InPlaceLinearPivoting (size_t &rank, Element &determinant, _Matrix &A, size_t Ni, size_t Nj) const |
| Sparse in place Gaussian elimination with reordering to reduce fill-in. | |
| template<class _Matrix, class Perm> | |
| size_t & | InPlaceLinearPivoting (size_t &rank, Element &determinant, _Matrix &A, Perm &P, size_t Ni, size_t Nj) const |
| Sparse in place Gaussian elimination with reordering to reduce fill-in. | |
| template<class _Matrix> | |
| size_t & | NoReordering (size_t &rank, Element &determinant, _Matrix &LigneA, size_t Ni, size_t Nj) const |
| Sparse Gaussian elimination without reordering. | |
| template<class _Matrix> | |
| size_t & | LUin (size_t &rank, _Matrix &A) const |
| Dense in place LU factorization without reordering. | |
| template<class _Matrix> | |
| size_t & | upperin (size_t &rank, _Matrix &A) const |
| Dense in place Gaussian elimination without reordering. | |
| template<class Vector, class D> | |
| void | eliminate (Element &headpivot, Vector &lignecourante, const Vector &lignepivot, const size_t indcol, const long indpermut, const size_t npiv, D &columns) const |
| Sparse in place Gaussian elimination with reordering to reduce fill-in. | |
| template<class Vector, class D> | |
| void | eliminate (Vector &lignecourante, const Vector &lignepivot, const size_t &indcol, const long &indpermut, D &columns) const |
| Sparse in place Gaussian elimination with reordering to reduce fill-in. | |
| template<class Vector> | |
| void | eliminate (Vector &lignecourante, const Vector &lignepivot, const size_t &indcol, const long &indpermut) const |
| Sparse in place Gaussian elimination with reordering to reduce fill-in. | |
| template<class Vector> | |
| void | permute (Vector &lignecourante, const size_t &indcol, const long &indpermut) const |
| Sparse in place Gaussian elimination with reordering to reduce fill-in. | |
| template<class Vector> | |
| void | Upper (Vector &lignecur, const Vector &lignepivot, size_t indcol, long indpermut) const |
| Sparse in place Gaussian elimination with reordering to reduce fill-in. | |
| template<class Vector> | |
| void | LU (Vector &lignecur, const Vector &lignepivot, size_t indcol, long indpermut) const |
| Sparse in place Gaussian elimination with reordering to reduce fill-in. | |
| template<class Vector, class D> | |
| void | SparseFindPivot (Vector &lignepivot, size_t &indcol, long &indpermut, D &columns, Element &determinant) const |
| Sparse in place Gaussian elimination with reordering to reduce fill-in. | |
| template<class Vector> | |
| void | SparseFindPivot (Vector &lignepivot, size_t &indcol, long &indpermut, Element &determinant) const |
| Sparse in place Gaussian elimination with reordering to reduce fill-in. | |
| template<class Vector> | |
| void | FindPivot (Vector &lignepivot, size_t &k, long &indpermut) const |
| Sparse in place Gaussian elimination with reordering to reduce fill-in. | |
| template<class _Matrix, class Perm> | |
| size_t & | SparseContinuation (size_t &rank, Element &determinant, std::deque< std::pair< size_t, size_t > > &invQ, _Matrix &L, _Matrix &U, Perm &P, size_t Ni, size_t Nj) const |
| Sparse in place Gaussian elimination with reordering to reduce fill-in. | |
Detailed Description
class LinBox::PowerGaussDomain< _Field >
Repository of functions for rank modulo a prime power by elimination on sparse matrices.
- Examples
- examples/power_rank.C, and examples/smithsparse.C.
Member Function Documentation
◆ MY_Zpz_inv_classic()
|
inline |
clang complains for examples/smith.C and examples/smithvalence.C
◆ detInPlace() [1/2]
|
inlineinherited |
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.
- Precondition
- 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
- Bibliography
- Jean-Guillaume Dumas and Gilles Villard, Computing the rank of sparse matrices over finite fields. In Ganzha et~al. CASC'2002, pages 47–62.
◆ detInPlace() [2/2]
|
inlineinherited |
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.
- Precondition
- 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
- Bibliography
- Jean-Guillaume Dumas and Gilles Villard, Computing the rank of sparse matrices over finite fields. In Ganzha et~al. CASC'2002, pages 47–62.
◆ det() [1/2]
|
inlineinherited |
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.
- Precondition
- 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
- Bibliography
- Jean-Guillaume Dumas and Gilles Villard, Computing the rank of sparse matrices over finite fields. In Ganzha et~al. CASC'2002, pages 47–62.
◆ det() [2/2]
|
inlineinherited |
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.
- Precondition
- 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
- Bibliography
- Jean-Guillaume Dumas and Gilles Villard, Computing the rank of sparse matrices over finite fields. In Ganzha et~al. CASC'2002, pages 47–62.
◆ QLUPin()
|
inlineinherited |
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.
- Precondition
- 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
- Bibliography
- Jean-Guillaume Dumas and Gilles Villard, Computing the rank of sparse matrices over finite fields. In Ganzha et~al. CASC'2002, pages 47–62.
◆ DenseQLUPin()
|
inlineinherited |
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.
- Precondition
- 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
- Bibliography
- Jean-Guillaume Dumas and Gilles Villard, Computing the rank of sparse matrices over finite fields. In Ganzha et~al. CASC'2002, pages 47–62.
◆ solve()
|
inlineinherited |
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.
- Precondition
- 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
- Bibliography
- Jean-Guillaume Dumas and Gilles Villard, Computing the rank of sparse matrices over finite fields. In Ganzha et~al. CASC'2002, pages 47–62.
◆ solveInPlace() [1/2]
|
inlineinherited |
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.
- Precondition
- 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
- Bibliography
- Jean-Guillaume Dumas and Gilles Villard, Computing the rank of sparse matrices over finite fields. In Ganzha et~al. CASC'2002, pages 47–62.
◆ solveInPlace() [2/2]
|
inlineinherited |
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.
- Precondition
- 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
- Bibliography
- Jean-Guillaume Dumas and Gilles Villard, Computing the rank of sparse matrices over finite fields. In Ganzha et~al. CASC'2002, pages 47–62.
◆ nullspacebasis() [1/2]
|
inlineinherited |
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.
- Precondition
- 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
- Bibliography
- Jean-Guillaume Dumas and Gilles Villard, Computing the rank of sparse matrices over finite fields. In Ganzha et~al. CASC'2002, pages 47–62.
◆ nullspacebasis() [2/2]
|
inlineinherited |
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.
- Precondition
- 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
- Bibliography
- Jean-Guillaume Dumas and Gilles Villard, Computing the rank of sparse matrices over finite fields. In Ganzha et~al. CASC'2002, pages 47–62.
◆ nullspacebasisin()
|
inlineinherited |
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.
- Precondition
- 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
- Bibliography
- Jean-Guillaume Dumas and Gilles Villard, Computing the rank of sparse matrices over finite fields. In Ganzha et~al. CASC'2002, pages 47–62.
- Examples
- examples/nullspacebasis.C.
◆ InPlaceLinearPivoting() [1/2]
|
inlineinherited |
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.
- Precondition
- 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
- Bibliography
- Jean-Guillaume Dumas and Gilles Villard, Computing the rank of sparse matrices over finite fields. In Ganzha et~al. CASC'2002, pages 47–62.
◆ InPlaceLinearPivoting() [2/2]
|
inlineinherited |
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.
- Precondition
- 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
- Bibliography
- Jean-Guillaume Dumas and Gilles Villard, Computing the rank of sparse matrices over finite fields. In Ganzha et~al. CASC'2002, pages 47–62.
◆ NoReordering()
|
inlineinherited |
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)
◆ LUin()
|
inlineinherited |
Dense in place LU factorization without reordering.
Using : FindPivot and LU
◆ upperin()
|
inlineinherited |
Dense in place Gaussian elimination without reordering.
Using : FindPivot and LU
◆ eliminate() [1/3]
|
inlineprotectedinherited |
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.
- Precondition
- 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
- Bibliography
- Jean-Guillaume Dumas and Gilles Villard, Computing the rank of sparse matrices over finite fields. In Ganzha et~al. CASC'2002, pages 47–62.
◆ eliminate() [2/3]
|
inlineprotectedinherited |
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.
- Precondition
- 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
- Bibliography
- Jean-Guillaume Dumas and Gilles Villard, Computing the rank of sparse matrices over finite fields. In Ganzha et~al. CASC'2002, pages 47–62.
◆ eliminate() [3/3]
|
inlineprotectedinherited |
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.
- Precondition
- 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
- Bibliography
- Jean-Guillaume Dumas and Gilles Villard, Computing the rank of sparse matrices over finite fields. In Ganzha et~al. CASC'2002, pages 47–62.
◆ permute()
|
inlineprotectedinherited |
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.
- Precondition
- 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
- Bibliography
- Jean-Guillaume Dumas and Gilles Villard, Computing the rank of sparse matrices over finite fields. In Ganzha et~al. CASC'2002, pages 47–62.
◆ Upper()
|
inlineprotectedinherited |
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.
- Precondition
- 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
- Bibliography
- Jean-Guillaume Dumas and Gilles Villard, Computing the rank of sparse matrices over finite fields. In Ganzha et~al. CASC'2002, pages 47–62.
◆ LU()
|
inlineprotectedinherited |
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.
- Precondition
- 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
- Bibliography
- Jean-Guillaume Dumas and Gilles Villard, Computing the rank of sparse matrices over finite fields. In Ganzha et~al. CASC'2002, pages 47–62.
◆ SparseFindPivot() [1/2]
|
inlineprotectedinherited |
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.
- Precondition
- 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
- Bibliography
- Jean-Guillaume Dumas and Gilles Villard, Computing the rank of sparse matrices over finite fields. In Ganzha et~al. CASC'2002, pages 47–62.
◆ SparseFindPivot() [2/2]
|
inlineprotectedinherited |
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.
- Precondition
- 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
- Bibliography
- Jean-Guillaume Dumas and Gilles Villard, Computing the rank of sparse matrices over finite fields. In Ganzha et~al. CASC'2002, pages 47–62.
◆ FindPivot()
|
inlineprotectedinherited |
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.
- Precondition
- 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
- Bibliography
- Jean-Guillaume Dumas and Gilles Villard, Computing the rank of sparse matrices over finite fields. In Ganzha et~al. CASC'2002, pages 47–62.
◆ SparseContinuation()
|
inlineprotectedinherited |
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.
- Precondition
- 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
- Bibliography
- Jean-Guillaume Dumas and Gilles Villard, Computing the rank of sparse matrices over finite fields. In Ganzha et~al. CASC'2002, pages 47–62.
The documentation for this class was generated from the following file:
- smith-form-sparseelim-local.h
Generated on Fri Jan 16 2026 00:40:00 for linbox by
1.13.2