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

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 >
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 LinearPivoting (by default) or NoReordering
template<class _Matrix >
Element &	detInPlace (Element &determinant, _Matrix &A, PivotStrategy reord=PivotStrategy::Linear) const

template<class _Matrix >
Element &	detInPlace (Element &determinant, _Matrix &A, size_t Ni, size_t Nj, PivotStrategy reord=PivotStrategy::Linear) const

template<class _Matrix >
Element &	det (Element &determinant, const _Matrix &A, PivotStrategy reord=PivotStrategy::Linear) const

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

◆ QLUPin()

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

◆ NoReordering()

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

◆ LUin()

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

inline

Dense in place LU factorization without reordering.

Using : FindPivot and LU

◆ upperin()

size_t & upperin	(	size_t &	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:

gauss.h
gauss-det.inl
gauss-elim.inl
gauss-nullspace.inl
gauss-pivot.inl
gauss-rank.inl
gauss-solve.inl
gauss.inl

Public Member Functions

Detailed Description

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

Member Function Documentation

◆ QLUPin()

◆ NoReordering()

◆ LUin()

◆ upperin()

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