linbox
Public Member Functions
GaussDomain< _Field > Class Template Reference

Repository of functions for rank by elimination on sparse matrices. More...

#include <gauss.h>

+ Inheritance diagram for GaussDomain< _Field >:

Public Member Functions

 GaussDomain (const Field &F)
 The field parameter is the domain over which to perform computations.
 
const Field & field () const
 accessor for the field of computation
 
template<class Matrix , class Perm >
unsigned long & QLUPin (unsigned long &rank, Element &determinant, Perm &Q, Matrix &L, Matrix &U, Perm &P, unsigned long Ni, unsigned long Nj) const
 Sparse in place Gaussian elimination with reordering to reduce fill-in. More...
 
template<class Matrix >
unsigned long & NoReordering (unsigned long &rank, Element &determinant, Matrix &LigneA, unsigned long Ni, unsigned long Nj) const
 Sparse Gaussian elimination without reordering. More...
 
template<class Matrix >
unsigned long & LUin (unsigned long &rank, Matrix &A) const
 Dense in place LU factorization without reordering. More...
 
template<class Matrix >
unsigned long & upperin (unsigned long &rank, Matrix &A) const
 Dense in place Gaussian elimination without reordering. More...
 
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) const
 
template<class Matrix >
unsigned long & rankin (unsigned long &rank, Matrix &A, unsigned long Ni, unsigned long Nj, SparseEliminationTraits::PivotStrategy reord=SparseEliminationTraits::PIVOT_LINEAR) const
 
template<class Matrix >
unsigned long & rank (unsigned long &rank, const Matrix &A, SparseEliminationTraits::PivotStrategy reord=SparseEliminationTraits::PIVOT_LINEAR) const
 
template<class Matrix >
unsigned long & rank (unsigned long &rank, const Matrix &A, unsigned long Ni, unsigned long Nj, SparseEliminationTraits::PivotStrategy reord=SparseEliminationTraits::PIVOT_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 LinearPivoting (by default) or NoReordering

template<class Matrix >
Element & detin (Element &determinant, Matrix &A, SparseEliminationTraits::PivotStrategy reord=SparseEliminationTraits::PIVOT_LINEAR) const
 
template<class Matrix >
Element & detin (Element &determinant, Matrix &A, unsigned long Ni, unsigned long Nj, SparseEliminationTraits::PivotStrategy reord=SparseEliminationTraits::PIVOT_LINEAR) const
 
template<class Matrix >
Element & det (Element &determinant, const Matrix &A, SparseEliminationTraits::PivotStrategy reord=SparseEliminationTraits::PIVOT_LINEAR) const
 
template<class Matrix >
Element & det (Element &determinant, const Matrix &A, unsigned long Ni, unsigned long Nj, SparseEliminationTraits::PivotStrategy reord=SparseEliminationTraits::PIVOT_LINEAR) const
 

Detailed Description

template<class _Field>
class LinBox::GaussDomain< _Field >

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.

Member Function Documentation

unsigned long & QLUPin ( unsigned long &  rank,
Element &  determinant,
Perm &  Q,
Matrix &  L,
Matrix &  U,
Perm &  P,
unsigned long  Ni,
unsigned long  Nj 
) const
inline

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.
unsigned long & NoReordering ( unsigned long &  rank,
Element &  determinant,
Matrix &  LigneA,
unsigned long  Ni,
unsigned long  Nj 
) const
inline

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 
) const
inline

Dense in place LU factorization without reordering.

Using : FindPivot and LU

unsigned long & upperin ( unsigned long &  rank,
Matrix &  A 
) const
inline

Dense in place Gaussian elimination without reordering.

Using : FindPivot and LU


The documentation for this class was generated from the following files: