linbox
Public Member Functions
PowerGaussDomain< _Field > Class Template Reference

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 >:
+ Collaboration 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

template<class _Matrix >
size_t & rankInPlace (size_t &rank, _Matrix &A, PivotStrategy reord=PivotStrategy::Linear) const
 
template<class _Matrix >
size_t & rankInPlace (size_t &rank, _Matrix &A, size_t Ni, size_t Nj, PivotStrategy reord=PivotStrategy::Linear) const
 
template<class _Matrix >
size_t & rank (size_t &rank, const _Matrix &A, PivotStrategy reord=PivotStrategy::Linear) const
 
template<class _Matrix >
size_t & rank (size_t &rank, const _Matrix &A, size_t Ni, size_t Nj, PivotStrategy reord=PivotStrategy::Linear) const
 

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. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
template<class _Matrix , class Block >
Block & nullspacebasis (Block &x, const _Matrix &A) const
 Sparse in place Gaussian elimination with reordering to reduce fill-in. More...
 
template<class _Matrix , class Block >
Block & nullspacebasisin (Block &x, _Matrix &A) const
 Sparse in place Gaussian elimination with reordering to reduce fill-in. More...
 
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. More...
 
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. More...
 
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. More...
 
template<class _Matrix >
size_t & LUin (size_t &rank, _Matrix &A) const
 Dense in place LU factorization without reordering. More...
 
template<class _Matrix >
size_t & upperin (size_t &rank, _Matrix &A) const
 Dense in place Gaussian elimination without reordering. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
template<class Vector >
void FindPivot (Vector &lignepivot, size_t &k, long &indpermut) const
 Sparse in place Gaussian elimination with reordering to reduce fill-in. More...
 
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. More...
 

Detailed Description

template<class _Field>
class LinBox::PowerGaussDomain< _Field >

Repository of functions for rank modulo a prime power by elimination on sparse matrices.

Examples
examples/smithsparse.C.

Member Function Documentation

◆ MY_Zpz_inv_classic()

Modulo& MY_Zpz_inv_classic ( Modulo &  u1,
const Modulo2  a,
const Modulo3  _p 
) const
inline

clang complains for examples/smith.C and examples/smithvalence.C

◆ detInPlace() [1/2]

GaussDomain< _Field >::Element & detInPlace ( Element &  determinant,
_Matrix &  A,
PivotStrategy  reord = PivotStrategy::Linear 
) const
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]

GaussDomain< _Field >::Element & detInPlace ( Element &  determinant,
_Matrix &  A,
size_t  Ni,
size_t  Nj,
PivotStrategy  reord = PivotStrategy::Linear 
) const
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]

GaussDomain< _Field >::Element & det ( Element &  determinant,
const _Matrix &  A,
PivotStrategy  reord = PivotStrategy::Linear 
) const
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]

GaussDomain< _Field >::Element & det ( Element &  determinant,
const _Matrix &  A,
size_t  Ni,
size_t  Nj,
PivotStrategy  reord = PivotStrategy::Linear 
) const
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()

size_t & QLUPin ( size_t &  rank,
Element &  determinant,
Perm &  Q,
_Matrix &  L,
_Matrix &  U,
Perm &  P,
size_t  Ni,
size_t  Nj 
) const
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()

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
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()

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
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]

Vector1 & solveInPlace ( Vector1 &  x,
_Matrix &  A,
const Vector2 &  b 
) const
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]

Vector1 & solveInPlace ( Vector1 &  x,
_Matrix &  A,
const Vector2 &  b,
Random &  generator 
) const
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]

Block & nullspacebasis ( Block &  x,
size_t  rank,
const _Matrix &  U,
const Perm &  P 
) const
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]

Block & nullspacebasis ( Block &  x,
const _Matrix &  A 
) const
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()

Block & nullspacebasisin ( Block &  x,
_Matrix &  A 
) const
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() [1/2]

size_t & InPlaceLinearPivoting ( size_t &  rank,
Element &  determinant,
_Matrix &  A,
size_t  Ni,
size_t  Nj 
) const
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]

size_t & InPlaceLinearPivoting ( size_t &  rank,
Element &  determinant,
_Matrix &  A,
Perm &  P,
size_t  Ni,
size_t  Nj 
) const
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()

size_t & NoReordering ( size_t &  rank,
Element &  determinant,
_Matrix &  LigneA,
size_t  Ni,
size_t  Nj 
) const
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()

size_t & LUin ( size_t &  rank,
_Matrix &  A 
) const
inlineinherited

Dense in place LU factorization without reordering.

Using : FindPivot and LU

◆ upperin()

size_t & upperin ( size_t &  rank,
_Matrix &  A 
) const
inlineinherited

Dense in place Gaussian elimination without reordering.

Using : FindPivot and LU

◆ eliminate() [1/3]

void eliminate ( Element &  headpivot,
Vector lignecourante,
const Vector lignepivot,
const size_t  indcol,
const long  indpermut,
const size_t  npiv,
D &  columns 
) const
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]

void eliminate ( Vector lignecourante,
const Vector lignepivot,
const size_t &  indcol,
const long &  indpermut,
D &  columns 
) const
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]

void eliminate ( Vector lignecourante,
const Vector lignepivot,
const size_t &  indcol,
const long &  indpermut 
) const
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()

void permute ( Vector lignecourante,
const size_t &  indcol,
const long &  indpermut 
) const
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()

void Upper ( Vector lignecur,
const Vector lignepivot,
size_t  indcol,
long  indpermut 
) const
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()

void LU ( Vector lignecur,
const Vector lignepivot,
size_t  indcol,
long  indpermut 
) const
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]

void SparseFindPivot ( Vector lignepivot,
size_t &  indcol,
long &  indpermut,
D &  columns,
Element &  determinant 
) const
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]

void SparseFindPivot ( Vector lignepivot,
size_t &  indcol,
long &  indpermut,
Element &  determinant 
) const
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()

void FindPivot ( Vector lignepivot,
size_t &  k,
long &  indpermut 
) const
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()

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
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: