linbox  1
Public Types | Public Member Functions
Eliminator< Field, Matrix > Class Template Reference

#include <eliminator.h>

List of all members.

Public Types

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

Public Member Functions

 Eliminator (const Field &F, unsigned int N)
 ~Eliminator ()
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)
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)
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)
double getTotalTime () const
double getInvertTime () const
std::ostream & writeFilter (std::ostream &out, const std::vector< bool > &v) const
std::ostream & writePermutation (std::ostream &out, const Permutation &P) const

Detailed Description

template<class Field, class Matrix = DenseMatrixBase<typename Field::Element>>
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
traitsSolverTraits} structure describing user options for the solver
~Eliminator ( )

Destructor


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
leftPriorityIdxPriority indices on the left
RightpriorityidxPriority indices on the right
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
Returns:
Reference to U
double getTotalTime ( ) const [inline]

Retrieve the total user time spent permuting and inverting

double getInvertTime ( ) const [inline]

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


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