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 Types
using	Matrix = SparseMatrix<Field, SparseMatrixFormat::SparseSeq>

Public Member Functions
	PowerGaussDomain (const Field &F)
	The field parameter is the domain over which to perform computations.

	PowerGaussDomain (const PowerGaussDomain &M)

template<class Modulu>
bool	isNZero (const Modulu &a) const

template<class Modulu>
bool	isZero (const Modulu &a) const

template<class Modulo, class Modulo2, class Modulo3>
Modulo &	MY_Zpz_inv_classic (Modulo &u1, const Modulo2 a, const Modulo3 _p) const

template<class Modulo, class Modulo2, class Modulo3>
Modulo &	MY_Zpz_inv (Modulo &v1, const Modulo2 &a, const Modulo3 &_p, const Modulo3 &_q, uint64_t exponent) const

template<class Ring1, class Ring2>
bool	MY_divides (Ring1 a, Ring2 b) const

template<class Modulo, class Vecteur, class D>
void	SameColumnPivoting (Modulo PRIME, const Vecteur &lignepivot, size_t &indcol, long &indpermut, D &columns, Boolean_Trait< false >::BooleanType)

template<class Modulo, class Vecteur, class D>
void	SameColumnPivoting (Modulo PRIME, const Vecteur &lignepivot, size_t &indcol, long &indpermut, D &columns, Boolean_Trait< true >::BooleanType)

template<class Modulo, class BB, class Mmap, class D>
bool	SameColumnPivotingTrait (Modulo PRIME, size_t &p, const BB &LigneA, const Mmap &psizes, size_t &indcol, long &indpermut, D &columns, Boolean_Trait< false >::BooleanType)

template<class Modulo, class BB, class Mmap, class D>
bool	SameColumnPivotingTrait (Modulo PRIME, size_t &p, const BB &LigneA, const Mmap &psizes, size_t &indcol, long &c, D &columns, Boolean_Trait< true >::BooleanType truetrait)

template<class Modulo, class Vecteur, class D>
void	CherchePivot (Modulo PRIME, Vecteur &lignepivot, size_t &indcol, long &indpermut, D &columns)

template<class Vecteur>
void	PermuteColumn (Vecteur &lignecourante, const size_t &nj, const size_t &k, const long &indpermut)

template<class SpMat>
void	PermuteSubMatrix (SpMat &LigneA, const size_t &start, const size_t &stop, const size_t &currentrank, const long &c)

template<class SpMat>
void	PermuteUpperMatrix (SpMat &LigneA, const size_t &k, const size_t &currentrank, const long &c, Boolean_Trait< true >::BooleanType)

template<class SpMat>
void	PermuteUpperMatrix (SpMat &, const size_t &, const size_t &, const long &, Boolean_Trait< false >::BooleanType)

template<class Vecteur>
void	PreserveUpperMatrixRow (Vecteur &ligne, Boolean_Trait< true >::BooleanType)

template<class Vecteur>
void	PreserveUpperMatrixRow (Vecteur &ligne, Boolean_Trait< false >::BooleanType)

template<class Modulo, class Vecteur, class De>
void	FaireElimination (Modulo MOD, Vecteur &lignecourante, const Vecteur &lignepivot, const typename Signed_Trait< Modulo >::unsigned_type &invpiv, const size_t &k, const long &indpermut, De &columns)

template<class Modulo, class BB, class D, class Container, class Perm, bool PrivilegiateNoColumnPivoting, bool PreserveUpperMatrix>
void	gauss_rankin (Modulo FMOD, Modulo PRIME, Container &ranks, BB &LigneA, Perm &Q, const size_t Ni, const size_t Nj, const D &density_trait)

template<class Modulo, class BB, class D, class Container, class Perm>
void	prime_power_rankin (Modulo FMOD, Modulo PRIME, Container &ranks, BB &SLA, Perm &Q, const size_t Ni, const size_t Nj, const D &density_trait, int StaticParameters=PRIVILEGIATE_NO_COLUMN_PIVOTING)

template<class Modulo, class Matrix, class Perm, template< class, class > class Container, template< class > class Alloc>
Container< std::pair< Modulo, size_t >, Alloc< std::pair< Modulo, size_t > > > &	operator() (Container< std::pair< Modulo, size_t >, Alloc< std::pair< Modulo, size_t > > > &L, Matrix &A, Perm &Q, Modulo FMOD, Modulo PRIME, int StaticParameters=PRIVILEGIATE_NO_COLUMN_PIVOTING)

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.

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

template<class _Field>
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 Typedef Documentation

◆ Matrix

template<class _Field>

using Matrix = SparseMatrix<Field, SparseMatrixFormat::SparseSeq>

inherited

Constructor & Destructor Documentation

◆ PowerGaussDomain() [1/2]

template<class _Field>

PowerGaussDomain ( const Field & F )

inline

The field parameter is the domain over which to perform computations.

◆ PowerGaussDomain() [2/2]

template<class _Field>

PowerGaussDomain ( const PowerGaussDomain< _Field > & M )

inline

Member Function Documentation

◆ isNZero()

template<class _Field>

template<class Modulu>

bool isNZero ( const Modulu & a ) const

inline

◆ isZero()

template<class _Field>

template<class Modulu>

bool isZero ( const Modulu & a ) const

inline

◆ MY_Zpz_inv_classic()

template<class _Field>

template<class Modulo, class Modulo2, class Modulo3>

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

◆ MY_Zpz_inv()

template<class _Field>

template<class Modulo, class Modulo2, class Modulo3>

Modulo & MY_Zpz_inv	(	Modulo &	v1,
		const Modulo2 &	a,
		const Modulo3 &	_p,
		const Modulo3 &	_q,
		uint64_t	exponent ) const

inline

◆ MY_divides()

template<class _Field>

template<class Ring1, class Ring2>

bool MY_divides	(	Ring1	a,
		Ring2	b ) const

inline

◆ SameColumnPivoting() [1/2]

template<class _Field>

template<class Modulo, class Vecteur, class D>

void SameColumnPivoting	(	Modulo	PRIME,
		const Vecteur &	lignepivot,
		size_t &	indcol,
		long &	indpermut,
		D &	columns,
		Boolean_Trait< false >::BooleanType	)

inline

◆ SameColumnPivoting() [2/2]

template<class _Field>

template<class Modulo, class Vecteur, class D>

void SameColumnPivoting	(	Modulo	PRIME,
		const Vecteur &	lignepivot,
		size_t &	indcol,
		long &	indpermut,
		D &	columns,
		Boolean_Trait< true >::BooleanType	)

inline

◆ SameColumnPivotingTrait() [1/2]

template<class _Field>

template<class Modulo, class BB, class Mmap, class D>

bool SameColumnPivotingTrait	(	Modulo	PRIME,
		size_t &	p,
		const BB &	LigneA,
		const Mmap &	psizes,
		size_t &	indcol,
		long &	indpermut,
		D &	columns,
		Boolean_Trait< false >::BooleanType	)

inline

◆ SameColumnPivotingTrait() [2/2]

template<class _Field>

template<class Modulo, class BB, class Mmap, class D>

bool SameColumnPivotingTrait	(	Modulo	PRIME,
		size_t &	p,
		const BB &	LigneA,
		const Mmap &	psizes,
		size_t &	indcol,
		long &	c,
		D &	columns,
		Boolean_Trait< true >::BooleanType	truetrait )

inline

◆ CherchePivot()

template<class _Field>

template<class Modulo, class Vecteur, class D>

void CherchePivot	(	Modulo	PRIME,
		Vecteur &	lignepivot,
		size_t &	indcol,
		long &	indpermut,
		D &	columns )

inline

◆ PermuteColumn()

template<class _Field>

template<class Vecteur>

void PermuteColumn	(	Vecteur &	lignecourante,
		const size_t &	nj,
		const size_t &	k,
		const long &	indpermut )

inline

◆ PermuteSubMatrix()

template<class _Field>

template<class SpMat>

void PermuteSubMatrix	(	SpMat &	LigneA,
		const size_t &	start,
		const size_t &	stop,
		const size_t &	currentrank,
		const long &	c )

inline

◆ PermuteUpperMatrix() [1/2]

template<class _Field>

template<class SpMat>

void PermuteUpperMatrix	(	SpMat &	LigneA,
		const size_t &	k,
		const size_t &	currentrank,
		const long &	c,
		Boolean_Trait< true >::BooleanType	)

inline

◆ PermuteUpperMatrix() [2/2]

template<class _Field>

template<class SpMat>

void PermuteUpperMatrix	(	SpMat &	,
		const size_t &	,
		const size_t &	,
		const long &	,
		Boolean_Trait< false >::BooleanType	)

inline

◆ PreserveUpperMatrixRow() [1/2]

template<class _Field>

template<class Vecteur>

void PreserveUpperMatrixRow	(	Vecteur &	ligne,
		Boolean_Trait< true >::BooleanType	)

inline

◆ PreserveUpperMatrixRow() [2/2]

template<class _Field>

template<class Vecteur>

void PreserveUpperMatrixRow	(	Vecteur &	ligne,
		Boolean_Trait< false >::BooleanType	)

inline

◆ FaireElimination()

template<class _Field>

template<class Modulo, class Vecteur, class De>

void FaireElimination	(	Modulo	MOD,
		Vecteur &	lignecourante,
		const Vecteur &	lignepivot,
		const typename Signed_Trait< Modulo >::unsigned_type &	invpiv,
		const size_t &	k,
		const long &	indpermut,
		De &	columns )

inline

◆ gauss_rankin()

template<class _Field>

template<class Modulo, class BB, class D, class Container, class Perm, bool PrivilegiateNoColumnPivoting, bool PreserveUpperMatrix>

void gauss_rankin	(	Modulo	FMOD,
		Modulo	PRIME,
		Container &	ranks,
		BB &	LigneA,
		Perm &	Q,
		const size_t	Ni,
		const size_t	Nj,
		const D &	density_trait )

inline

◆ prime_power_rankin()

template<class _Field>

template<class Modulo, class BB, class D, class Container, class Perm>

void prime_power_rankin	(	Modulo	FMOD,
		Modulo	PRIME,
		Container &	ranks,
		BB &	SLA,
		Perm &	Q,
		const size_t	Ni,
		const size_t	Nj,
		const D &	density_trait,
		int	StaticParameters = PRIVILEGIATE_NO_COLUMN_PIVOTING )

inline

◆ operator()()

template<class _Field>

template<class Modulo, class Matrix, class Perm, template< class, class > class Container, template< class > class Alloc>

Container< std::pair< Modulo, size_t >, Alloc< std::pair< Modulo, size_t > > > & operator()	(	Container< std::pair< Modulo, size_t >, Alloc< std::pair< Modulo, size_t > > > &	L,
		Matrix &	A,
		Perm &	Q,
		Modulo	FMOD,
		Modulo	PRIME,
		int	StaticParameters = PRIVILEGIATE_NO_COLUMN_PIVOTING )

inline

◆ field()

template<class _Field>

const Field & field ( ) const

inlineinherited

accessor for the field of computation

◆ rankInPlace() [1/2]

template<class _Field>

template<class _Matrix>

size_t & rankInPlace	(	size_t &	rank,
		_Matrix &	A,
		PivotStrategy	reord = PivotStrategy::Linear ) const

inherited

◆ rankInPlace() [2/2]

template<class _Field>

template<class _Matrix>

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

inherited

◆ rank() [1/2]

template<class _Field>

template<class _Matrix>

size_t & rank	(	size_t &	rank,
		const _Matrix &	A,
		PivotStrategy	reord = PivotStrategy::Linear ) const

inherited

◆ rank() [2/2]

template<class _Field>

template<class _Matrix>

size_t & rank	(	size_t &	rank,
		const _Matrix &	A,
		size_t	Ni,
		size_t	Nj,
		PivotStrategy	reord = PivotStrategy::Linear ) const

inherited

◆ detInPlace() [1/2]

template<class _Field>

template<class _Matrix>

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]

template<class _Field>

template<class _Matrix>

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]

template<class _Field>

template<class _Matrix>

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]

template<class _Field>

template<class _Matrix>

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

template<class _Field>

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

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

template<class _Field>

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

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

template<class _Field>

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

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]

template<class _Field>

template<class _Matrix, class Vector1, class Vector2>

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]

template<class _Field>

template<class _Matrix, class Vector1, class Vector2, class Random>

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]

template<class _Field>

template<class _Matrix, class Perm, class Block>

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]

template<class _Field>

template<class _Matrix, class Block>

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

template<class _Field>

template<class _Matrix, class Block>

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.

Examples: examples/nullspacebasis.C.

◆ InPlaceLinearPivoting() [1/2]

template<class _Field>

template<class _Matrix>

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]

template<class _Field>

template<class _Matrix, class Perm>

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

template<class _Field>

template<class _Matrix>

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

template<class _Field>

template<class _Matrix>

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

inlineinherited

Dense in place LU factorization without reordering.

Using : FindPivot and LU

◆ upperin()

template<class _Field>

template<class _Matrix>

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

inlineinherited

Dense in place Gaussian elimination without reordering.

Using : FindPivot and LU

◆ eliminate() [1/3]

template<class _Field>

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

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]

template<class _Field>

template<class Vector, class D>

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]

template<class _Field>

template<class Vector>

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

template<class _Field>

template<class Vector>

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

template<class _Field>

template<class Vector>

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

template<class _Field>

template<class Vector>

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]

template<class _Field>

template<class Vector, class D>

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]

template<class _Field>

template<class Vector>

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

template<class _Field>

template<class Vector>

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

template<class _Field>

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

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

Public Types

Public Member Functions

det

Detailed Description

Member Typedef Documentation

◆ Matrix

Constructor & Destructor Documentation

◆ PowerGaussDomain() [1/2]

◆ PowerGaussDomain() [2/2]

Member Function Documentation

◆ isNZero()

◆ isZero()

◆ MY_Zpz_inv_classic()

◆ MY_Zpz_inv()

◆ MY_divides()

◆ SameColumnPivoting() [1/2]

◆ SameColumnPivoting() [2/2]

◆ SameColumnPivotingTrait() [1/2]

◆ SameColumnPivotingTrait() [2/2]

◆ CherchePivot()

◆ PermuteColumn()

◆ PermuteSubMatrix()

◆ PermuteUpperMatrix() [1/2]

◆ PermuteUpperMatrix() [2/2]

◆ PreserveUpperMatrixRow() [1/2]

◆ PreserveUpperMatrixRow() [2/2]

◆ FaireElimination()

◆ gauss_rankin()

◆ prime_power_rankin()

◆ operator()()

◆ field()

◆ rankInPlace() [1/2]

◆ rankInPlace() [2/2]

◆ rank() [1/2]

◆ rank() [2/2]

◆ detInPlace() [1/2]

◆ detInPlace() [2/2]

◆ det() [1/2]

◆ det() [2/2]

◆ QLUPin()

◆ DenseQLUPin()

◆ solve()

◆ solveInPlace() [1/2]

◆ solveInPlace() [2/2]

◆ nullspacebasis() [1/2]

◆ nullspacebasis() [2/2]

◆ nullspacebasisin()

◆ InPlaceLinearPivoting() [1/2]

◆ InPlaceLinearPivoting() [2/2]

◆ NoReordering()

◆ LUin()

◆ upperin()

◆ eliminate() [1/3]

◆ eliminate() [2/3]

◆ eliminate() [3/3]

◆ permute()

◆ Upper()

◆ LU()

◆ SparseFindPivot() [1/2]

◆ SparseFindPivot() [2/2]

◆ FindPivot()

◆ SparseContinuation()