Elimination system. More...

#include <eliminator.h>

Public Types
typedef Field::Element	Element

typedef std::pair< unsigned int, unsigned int >	Transposition
	Permutation.

typedef std::vector< Transposition >	Permutation

Public Member Functions
	Eliminator (const Field &F, unsigned int N)
	Constructor.

	~Eliminator ()
	Destructor.

template<class Matrix1, class Matrix2, class Matrix3, class Matrix4>
void	twoSidedGaussJordan (Matrix1 &Ainv, Permutation &P, Matrix2 &Tu, Permutation &Q, Matrix3 &Tv, const Matrix4 &A, unsigned int &rank)
	Two-sided Gauss-Jordan transform.

Matrix &	permuteAndInvert (Matrix &W, std::vector< bool > &S, std::vector< bool > &T, std::list< unsigned int > &rightPriorityIdx, Permutation &Qp, unsigned int &rank, const Matrix &A)
	Permute the input and invert it.

template<class Matrix1, class Matrix2, class Matrix3, class Matrix4>
Matrix1 &	gaussJordan (Matrix1 &U, std::vector< unsigned int > &profile, Permutation &P, Matrix2 &Tu, Permutation &Q, Matrix3 &Tv, unsigned int &rank, typename Field::Element &det, const Matrix4 &A)
	Perform a Gauss-Jordan transform using a recursive algorithm.

double	getTotalTime () const
	Retrieve the total user time spent permuting and inverting.

double	getInvertTime () const
	Retrieve the total user time spent inverting only.

std::ostream &	writeFilter (std::ostream &out, const std::vector< bool > &v) const
	Write the filter vector to the given output stream.

std::ostream &	writePermutation (std::ostream &out, const Permutation &P) const
	Write the given permutation to the output stream.

const Field &	field ()

Matrix &	kthGaussJordan (unsigned int &r, typename Field::Element &d, unsigned int k, unsigned int s, unsigned int m, const typename Field::Element &d0)

template<class Matrix1>
Matrix1 &	setIN (Matrix1 &A) const

template<class Matrix1>
Matrix1 &	adddIN (Matrix1 &A, const typename Field::Element &d) const

void	cleanPriorityIndexList (std::list< unsigned int > &list, std::vector< bool > &S, std::vector< bool > &old_S) const

template<class Iterator>
std::vector< bool > &	permute (std::vector< bool > &v, Iterator P_start, Iterator P_end) const

Permutation &	buildPermutation (Permutation &P, const std::list< unsigned int > &pidx) const

Permutation &	buildMinimalPermutation (Permutation &P, unsigned int rank, unsigned int dim, const Permutation &Pold)

Permutation &	buildMinimalPermutationFromProfile (Permutation &P, unsigned int rank, unsigned int dim, const std::vector< unsigned int > &profile)

Detailed Description

template<class Field, class Matrix = BlasMatrix<Field>>
class LinBox::Eliminator< Field, Matrix >

Elimination system.

This is the supporting elimination system for a lookahead-based variant of block Lanczos.

Member Typedef Documentation

◆ Element

template<class Field, class Matrix = BlasMatrix<Field>>

typedef Field::Element Element

◆ Transposition

template<class Field, class Matrix = BlasMatrix<Field>>

typedef std::pair<unsigned int, unsigned int> Transposition

Permutation.

A permutation is represented as a vector of pairs, each pair representing a transposition. Thus a permutation requires O(n log n) storage and O(n log n) application time, as opposed to the lower bound of O(n) for both. However, this allows us to decompose a permutation easily into its factors, thus eliminating the need for additional auxillary storage in each level of the Gauss-Jordan transform recursion. Additionally, we expect to use this with dense matrices that are "close to generic", meaning that the rank should be high and there should be relatively little need for transpositions. In practice, we therefore expect this to beat the vector representation. The use of this representation does not affect the analysis of the Gauss-Jordan transform, since each step where a permutation is applied also requires matrix multiplication, which is strictly more expensive.

◆ Permutation

template<class Field, class Matrix = BlasMatrix<Field>>

typedef std::vector<Transposition> Permutation

Constructor & Destructor Documentation

◆ Eliminator()

template<class Field, class Matrix>

Eliminator	(	const Field &	F,
		unsigned int	N )

Constructor.

Parameters

F	Field over which to operate
N

◆ ~Eliminator()

template<class Field, class Matrix>

~Eliminator ( )

Destructor.

Member Function Documentation

◆ twoSidedGaussJordan()

template<class Field, class Matrix>

template<class Matrix1, class Matrix2, class Matrix3, class Matrix4>

void twoSidedGaussJordan	(	Matrix1 &	Ainv,
		Permutation &	P,
		Matrix2 &	Tu,
		Permutation &	Q,
		Matrix3 &	Tv,
		const Matrix4 &	A,
		unsigned int &	rank )

Two-sided Gauss-Jordan transform.

Parameters

Ainv	Inverse of nonsingular part of A
Tu	Row dependencies
Tv	Column dependencies
P	Row permutation
Q	Column permutation
A	Input matrix
rank	Rank of A

◆ permuteAndInvert()

template<class Field, class Matrix>

Matrix & permuteAndInvert	(	Matrix &	W,
		std::vector< bool > &	S,
		std::vector< bool > &	T,
		std::list< unsigned int > &	rightPriorityIdx,
		Permutation &	Qp,
		unsigned int &	rank,
		const Matrix &	A )

Permute the input and invert it.

Compute the pseudoinverse of the input matrix A and return it. First apply the permutation given by the lists leftPriorityIdx and rightPriorityIdx to the input matrix so that independent columns and rows are more likely to be found on the first indices in those lists. Zero out the rows and columns of the inverse corresponding to dependent rows and columns of the input. Set S and T to boolean vectors such that S^T A T is invertible and of maximal size.

Parameters

W	Output inverse
S	Output vector S
T	Output vector T
rightPriorityIdx	Priority indices on the right
Qp
rank
A	Input matrix A

Returns: Reference to inverse matrix

◆ gaussJordan()

template<class Field, class Matrix>

template<class Matrix1, class Matrix2, class Matrix3, class Matrix4>

Matrix1 & gaussJordan	(	Matrix1 &	U,
		std::vector< unsigned int > &	profile,
		Permutation &	P,
		Matrix2 &	Tu,
		Permutation &	Q,
		Matrix3 &	Tv,
		unsigned int &	rank,
		typename Field::Element &	det,
		const Matrix4 &	A )

Perform a Gauss-Jordan transform using a recursive algorithm.

Upon completion, we have UPA = R, where R is of reduced row echelon form

Parameters

U	Output matrix U
P	Output permutation P
A	Input matrix A
profile
Tu
Q
Tv
rank
det

Returns: Reference to U

◆ getTotalTime()

template<class Field, class Matrix = BlasMatrix<Field>>

double getTotalTime ( ) const

inline

Retrieve the total user time spent permuting and inverting.

◆ getInvertTime()

template<class Field, class Matrix = BlasMatrix<Field>>

double getInvertTime ( ) const

inline

Retrieve the total user time spent inverting only.

◆ writeFilter()

template<class Field, class Matrix>

std::ostream & writeFilter	(	std::ostream &	out,
		const std::vector< bool > &	v ) const

Write the filter vector to the given output stream.

◆ writePermutation()

template<class Field, class Matrix>

std::ostream & writePermutation	(	std::ostream &	out,
		const Permutation &	P ) const

Write the given permutation to the output stream.

◆ field()

template<class Field, class Matrix = BlasMatrix<Field>>

const Field & field ( )

inline

◆ kthGaussJordan()

template<class Field, class Matrix>

Matrix & kthGaussJordan	(	unsigned int &	r,
		typename Field::Element &	d,
		unsigned int	k,
		unsigned int	s,
		unsigned int	m,
		const typename Field::Element &	d0 )

◆ setIN()

template<class Field, class Matrix>

template<class Matrix1>

Matrix1 & setIN ( Matrix1 & A ) const

◆ adddIN()

template<class Field, class Matrix>

template<class Matrix1>

Matrix1 & adddIN	(	Matrix1 &	A,
		const typename Field::Element &	d ) const

◆ cleanPriorityIndexList()

template<class Field, class Matrix>

void cleanPriorityIndexList	(	std::list< unsigned int > &	list,
		std::vector< bool > &	S,
		std::vector< bool > &	old_S ) const

◆ permute()

template<class Field, class Matrix>

template<class Iterator>

std::vector< bool > & permute	(	std::vector< bool > &	v,
		Iterator	P_start,
		Iterator	P_end ) const

◆ buildPermutation()

template<class Field, class Matrix>

Eliminator< Field, Matrix >::Permutation & buildPermutation	(	Permutation &	P,
		const std::list< unsigned int > &	pidx ) const

◆ buildMinimalPermutation()

template<class Field, class Matrix>

Eliminator< Field, Matrix >::Permutation & buildMinimalPermutation	(	Permutation &	P,
		unsigned int	rank,
		unsigned int	dim,
		const Permutation &	Pold )

◆ buildMinimalPermutationFromProfile()

template<class Field, class Matrix>

Eliminator< Field, Matrix >::Permutation & buildMinimalPermutationFromProfile	(	Permutation &	P,
		unsigned int	rank,
		unsigned int	dim,
		const std::vector< unsigned int > &	profile )

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

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ Element

◆ Transposition

◆ Permutation

Constructor & Destructor Documentation

◆ Eliminator()

◆ ~Eliminator()

Member Function Documentation

◆ twoSidedGaussJordan()

◆ permuteAndInvert()

◆ gaussJordan()

◆ getTotalTime()

◆ getInvertTime()

◆ writeFilter()

◆ writePermutation()

◆ field()

◆ kthGaussJordan()

◆ setIN()

◆ adddIN()

◆ cleanPriorityIndexList()

◆ permute()

◆ buildPermutation()

◆ buildMinimalPermutation()

◆ buildMinimalPermutationFromProfile()