Eliminator< Field, Matrix > Class Template Reference

Elimination system. More...

#include <eliminator.h>

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

Public Member Functions
	Eliminator (const Field &F, unsigned int N)
	Constructor. More...
	~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. More...
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. More...
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. More...
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.

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

Transposition

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.

Constructor & Destructor Documentation

Eliminator()

Eliminator	(	const Field &	F,
		unsigned int	N
	)

Constructor.

Parameters

F	Field over which to operate
N

Member Function Documentation

twoSidedGaussJordan()

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

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

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

---

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

• eliminator.h
• eliminator.inl