linbox

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) 
Twosided GaussJordan 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 GaussJordan 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.  
Elimination system.
This is the supporting elimination system for a lookaheadbased variant of block Lanczos.
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 GaussJordan 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 GaussJordan transform, since each step where a permutation is applied also requires matrix multiplication, which is strictly more expensive.
Eliminator  (  const Field &  F, 
unsigned int  N  
) 
Constructor.
F  Field over which to operate 
N 
void twoSidedGaussJordan  (  Matrix1 &  Ainv, 
Permutation &  P,  
Matrix2 &  Tu,  
Permutation &  Q,  
Matrix3 &  Tv,  
const Matrix4 &  A,  
unsigned int &  rank  
) 
Twosided GaussJordan transform.
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 
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.
W  Output inverse 
S  Output vector S 
T  Output vector T 
rightPriorityIdx  Priority indices on the right 
Qp  
rank  
A  Input matrix A 
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 GaussJordan transform using a recursive algorithm.
Upon completion, we have UPA = R, where R is of reduced row echelon form
U  Output matrix U 
P  Output permutation P 
A  Input matrix A 
profile  
Tu  
Q  
Tv  
rank  
det 