linbox
Public Types | Public Member Functions
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

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 ( const Field &  F,
unsigned int  N 
)

Constructor.

Parameters
FField over which to operate
N

Member Function Documentation

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

Two-sided Gauss-Jordan transform.

Parameters
AinvInverse of nonsingular part of A
TuRow dependencies
TvColumn dependencies
PRow permutation
QColumn permutation
AInput matrix
rankRank of A
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
WOutput inverse
SOutput vector S
TOutput vector T
rightPriorityIdxPriority indices on the right
Qp
rank
AInput matrix A
Returns
Reference to inverse matrix
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
UOutput matrix U
POutput permutation P
AInput matrix A
profile
Tu
Q
Tv
rank
det
Returns
Reference to U

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