FFLAS-FFPACK
Data Structures | Functions
FFPACK Namespace Reference

Finite Field PACK Set of elimination based routines for dense linear algebra. More...

Data Structures

class  Failure
 A precondtion failed. More...
 

Functions

void LAPACKPerm2MathPerm (size_t *MathP, const size_t *LapackP, const size_t N)
 Conversion of a permutation from LAPACK format to Math format.
 
void MathPerm2LAPACKPerm (size_t *LapackP, const size_t *MathP, const size_t N)
 Conversion of a permutation from Maths format to LAPACK format.
 
void composePermutationsP (size_t *MathP, const size_t *P1, const size_t *P2, const size_t R, const size_t N)
 Computes P1 [ I_R ] stored in MathPermutation format [ P_2 ].
 
template<class Field >
void applyP (const Field &F, const FFLAS::FFLAS_SIDE Side, const FFLAS::FFLAS_TRANSPOSE Trans, const size_t M, const size_t ibeg, const size_t iend, typename Field::Element_ptr A, const size_t lda, const size_t *P)
 Apply a permutation P, stored in the LAPACK format (a sequence of transpositions) between indices ibeg and iend of P to (iend-ibeg) vectors of size M stored in A (as column for NoTrans and rows for Trans). More...
 
template<class Field >
void MonotonicApplyP (const Field &F, const FFLAS::FFLAS_SIDE Side, const FFLAS::FFLAS_TRANSPOSE Trans, const size_t M, const size_t ibeg, const size_t iend, typename Field::Element_ptr A, const size_t lda, const size_t *P, const size_t R)
 Apply a R-monotonically increasing permutation P, to the matrix A. More...
 
template<class Field >
void papplyP (const Field &F, const FFLAS::FFLAS_SIDE Side, const FFLAS::FFLAS_TRANSPOSE Trans, const size_t m, const size_t ibeg, const size_t iend, typename Field::Element_ptr A, const size_t lda, const size_t *P)
 Parallel applyP with OPENMP tasks.
 
template<class Field >
void pMatrixApplyT (const Field &F, typename Field::Element_ptr A, const size_t lda, const size_t width, const size_t N2, const size_t R1, const size_t R2, const size_t R3, const size_t R4)
 Parallel applyT with OPENMP tasks.
 
template<class Field >
void pMatrixApplyS (const Field &F, typename Field::Element_ptr A, const size_t lda, const size_t width, const size_t M2, const size_t R1, const size_t R2, const size_t R3, const size_t R4)
 Parallel applyS tasks with OPENMP tasks.
 
template<class Field >
void fgetrs (const Field &F, const FFLAS::FFLAS_SIDE Side, const size_t M, const size_t N, const size_t R, typename Field::Element_ptr A, const size_t lda, const size_t *P, const size_t *Q, typename Field::Element_ptr B, const size_t ldb, int *info)
 Solve the system $A X = B$ or $X A = B$. More...
 
template<class Field >
Field::Element_ptr fgetrs (const Field &F, const FFLAS::FFLAS_SIDE Side, const size_t M, const size_t N, const size_t NRHS, const size_t R, typename Field::Element_ptr A, const size_t lda, const size_t *P, const size_t *Q, typename Field::Element_ptr X, const size_t ldx, typename Field::ConstElement_ptr B, const size_t ldb, int *info)
 Solve the system A X = B or X A = B. More...
 
template<class Field >
size_t fgesv (const Field &F, const FFLAS::FFLAS_SIDE Side, const size_t M, const size_t N, typename Field::Element_ptr A, const size_t lda, typename Field::Element_ptr B, const size_t ldb, int *info)
 Square system solver. More...
 
template<class Field >
size_t fgesv (const Field &F, const FFLAS::FFLAS_SIDE Side, const size_t M, const size_t N, const size_t NRHS, typename Field::Element_ptr A, const size_t lda, typename Field::Element_ptr X, const size_t ldx, typename Field::ConstElement_ptr B, const size_t ldb, int *info)
 Rectangular system solver. More...
 
template<class Field >
void ftrtri (const Field &F, const FFLAS::FFLAS_UPLO Uplo, const FFLAS::FFLAS_DIAG Diag, const size_t N, typename Field::Element_ptr A, const size_t lda)
 Compute the inverse of a triangular matrix. More...
 
template<class Field >
void ftrtrm (const Field &F, const FFLAS::FFLAS_DIAG diag, const size_t N, typename Field::Element_ptr A, const size_t lda)
 Compute the product UL. More...
 
template<class Field >
size_t PLUQ (const Field &F, const FFLAS::FFLAS_DIAG Diag, const size_t M, const size_t N, typename Field::Element_ptr A, const size_t lda, size_t *P, size_t *Q)
 Compute the PLUQ factorization of the given matrix. More...
 
template<class Field >
size_t LUdivine (const Field &F, const FFLAS::FFLAS_DIAG Diag, const FFLAS::FFLAS_TRANSPOSE trans, const size_t M, const size_t N, typename Field::Element_ptr A, const size_t lda, size_t *P, size_t *Qt, const FFPACK_LU_TAG LuTag=FfpackSlabRecursive, const size_t cutoff=0)
 Compute the CUP factorization of the given matrix. More...
 
template<class Field >
size_t LUdivine_small (const Field &F, const FFLAS::FFLAS_DIAG Diag, const FFLAS::FFLAS_TRANSPOSE trans, const size_t M, const size_t N, typename Field::Element_ptr A, const size_t lda, size_t *P, size_t *Q, const FFPACK_LU_TAG LuTag=FfpackSlabRecursive)
 LUdivine small case.
 
template<class Field >
size_t LUdivine_gauss (const Field &F, const FFLAS::FFLAS_DIAG Diag, const size_t M, const size_t N, typename Field::Element_ptr A, const size_t lda, size_t *P, size_t *Q, const FFPACK_LU_TAG LuTag=FfpackSlabRecursive)
 LUdivine gauss.
 
template<class Field >
size_t ColumnEchelonForm (const Field &F, const size_t M, const size_t N, typename Field::Element_ptr A, const size_t lda, size_t *P, size_t *Qt, bool transform=false, const FFPACK_LU_TAG LuTag=FfpackSlabRecursive)
 Compute the Column Echelon form of the input matrix in-place. More...
 
template<class Field >
size_t RowEchelonForm (const Field &F, const size_t M, const size_t N, typename Field::Element_ptr A, const size_t lda, size_t *P, size_t *Qt, const bool transform=false, const FFPACK_LU_TAG LuTag=FfpackSlabRecursive)
 Compute the Row Echelon form of the input matrix in-place. More...
 
template<class Field >
size_t ReducedColumnEchelonForm (const Field &F, const size_t M, const size_t N, typename Field::Element_ptr A, const size_t lda, size_t *P, size_t *Qt, const bool transform=false, const FFPACK_LU_TAG LuTag=FfpackSlabRecursive)
 Compute the Reduced Column Echelon form of the input matrix in-place. More...
 
template<class Field >
size_t ReducedRowEchelonForm (const Field &F, const size_t M, const size_t N, typename Field::Element_ptr A, const size_t lda, size_t *P, size_t *Qt, const bool transform=false, const FFPACK_LU_TAG LuTag=FfpackSlabRecursive)
 Compute the Reduced Row Echelon form of the input matrix in-place. More...
 
template<class Field >
size_t ReducedRowEchelonForm2 (const Field &F, const size_t M, const size_t N, typename Field::Element_ptr A, const size_t lda, size_t *P, size_t *Qt, const bool transform=true)
 Variant by the block recursive algorithm. More...
 
template<class Field >
size_t REF (const Field &F, const size_t M, const size_t N, typename Field::Element_ptr A, const size_t lda, const size_t colbeg, const size_t rowbeg, const size_t colsize, size_t *Qt, size_t *P)
 REF. More...
 
template<class Field >
Field::Element_ptr Invert (const Field &F, const size_t M, typename Field::Element_ptr A, const size_t lda, int &nullity)
 Invert the given matrix in place or computes its nullity if it is singular. More...
 
template<class Field >
Field::Element_ptr Invert (const Field &F, const size_t M, typename Field::ConstElement_ptr A, const size_t lda, typename Field::Element_ptr X, const size_t ldx, int &nullity)
 Invert the given matrix in place or computes its nullity if it is singular. More...
 
template<class Field >
Field::Element_ptr Invert2 (const Field &F, const size_t M, typename Field::Element_ptr A, const size_t lda, typename Field::Element_ptr X, const size_t ldx, int &nullity)
 Invert the given matrix or computes its nullity if it is singular. More...
 
template<class Field , class Polynomial >
std::list< Polynomial > & CharPoly (const Field &F, std::list< Polynomial > &charp, const size_t N, typename Field::Element_ptr A, const size_t lda, const FFPACK_CHARPOLY_TAG CharpTag=FfpackArithProg)
 Compute the characteristic polynomial of A using Krylov Method, and LUP factorization of the Krylov matrix.
 
template<class Field , class Polynomial >
std::list< Polynomial > & CharpolyArithProg (const Field &F, std::list< Polynomial > &frobeniusForm, const size_t N, typename Field::Element_ptr A, const size_t lda, const size_t c)
 
template<class Field , class Polynomial >
Polynomial & MinPoly (const Field &F, Polynomial &minP, const size_t N, typename Field::ConstElement_ptr A, const size_t lda, typename Field::Element_ptr X, const size_t ldx, size_t *P, const FFPACK_MINPOLY_TAG MinTag=FFPACK::FfpackDense, const size_t kg_mc=0, const size_t kg_mb=0, const size_t kg_j=0)
 Compute the minimal polynomial. More...
 
template<class Field >
size_t Rank (const Field &F, const size_t M, const size_t N, typename Field::Element_ptr A, const size_t lda)
 Computes the rank of the given matrix using a LQUP factorization. More...
 
template<class Field >
bool IsSingular (const Field &F, const size_t M, const size_t N, typename Field::Element_ptr A, const size_t lda)
 Returns true if the given matrix is singular. More...
 
template<class Field >
Field::Element Det (const Field &F, const size_t M, const size_t N, typename Field::Element_ptr A, const size_t lda)
 Returns the determinant of the given matrix. More...
 
template<class Field >
Field::Element_ptr Solve (const Field &F, const size_t M, typename Field::Element_ptr A, const size_t lda, typename Field::Element_ptr x, const int incx, typename Field::ConstElement_ptr b, const int incb)
 Solve linear system using LQUP factorization.
 
template<class Field >
void solveLB (const Field &F, const FFLAS::FFLAS_SIDE Side, const size_t M, const size_t N, const size_t R, typename Field::Element_ptr L, const size_t ldl, const size_t *Q, typename Field::Element_ptr B, const size_t ldb)
 Solve L X = B or X L = B in place. More...
 
template<class Field >
void solveLB2 (const Field &F, const FFLAS::FFLAS_SIDE Side, const size_t M, const size_t N, const size_t R, typename Field::Element_ptr L, const size_t ldl, const size_t *Q, typename Field::Element_ptr B, const size_t ldb)
 Solve L X = B in place. More...
 
template<class Field >
void RandomNullSpaceVector (const Field &F, const FFLAS::FFLAS_SIDE Side, const size_t M, const size_t N, typename Field::Element_ptr A, const size_t lda, typename Field::Element_ptr X, const size_t incX)
 Computes a vector of the Left/Right nullspace of the matrix A. More...
 
template<class Field >
size_t NullSpaceBasis (const Field &F, const FFLAS::FFLAS_SIDE Side, const size_t M, const size_t N, typename Field::Element_ptr A, const size_t lda, typename Field::Element_ptr &NS, size_t &ldn, size_t &NSdim)
 Computes a basis of the Left/Right nullspace of the matrix A. More...
 
template<class Field >
size_t RowRankProfile (const Field &F, const size_t M, const size_t N, typename Field::Element_ptr A, const size_t lda, size_t *&rkprofile, const FFPACK_LU_TAG LuTag=FfpackSlabRecursive)
 Computes the row rank profile of A. More...
 
template<class Field >
size_t ColumnRankProfile (const Field &F, const size_t M, const size_t N, typename Field::Element_ptr A, const size_t lda, size_t *&rkprofile, const FFPACK_LU_TAG LuTag=FfpackSlabRecursive)
 Computes the column rank profile of A. More...
 
void RankProfileFromLU (const size_t *P, const size_t N, const size_t R, size_t *rkprofile, const FFPACK_LU_TAG LuTag)
 Recovers the column/row rank profile from the permutation of an LU decomposition. More...
 
size_t LeadingSubmatrixRankProfiles (const size_t M, const size_t N, const size_t R, const size_t LSm, const size_t LSn, const size_t *P, const size_t *Q, size_t *RRP, size_t *CRP)
 Recovers the row and column rank profiles of any leading submatrix from the PLUQ decomposition. More...
 
template<class Field >
size_t RowRankProfileSubmatrixIndices (const Field &F, const size_t M, const size_t N, typename Field::Element_ptr A, const size_t lda, size_t *&rowindices, size_t *&colindices, size_t &R)
 RowRankProfileSubmatrixIndices. More...
 
template<class Field >
size_t ColRankProfileSubmatrixIndices (const Field &F, const size_t M, const size_t N, typename Field::Element_ptr A, const size_t lda, size_t *&rowindices, size_t *&colindices, size_t &R)
 Computes the indices of the submatrix r*r X of A whose columns correspond to the column rank profile of A. More...
 
template<class Field >
size_t RowRankProfileSubmatrix (const Field &F, const size_t M, const size_t N, typename Field::Element_ptr A, const size_t lda, typename Field::Element_ptr &X, size_t &R)
 Computes the r*r submatrix X of A, by picking the row rank profile rows of A. More...
 
template<class Field >
size_t ColRankProfileSubmatrix (const Field &F, const size_t M, const size_t N, typename Field::Element_ptr A, const size_t lda, typename Field::Element_ptr &X, size_t &R)
 Compute the $ r\times r$ submatrix X of A, by picking the row rank profile rows of A. More...
 
template<class Field >
void getTriangular (const Field &F, const FFLAS::FFLAS_UPLO Uplo, const FFLAS::FFLAS_DIAG diag, const size_t M, const size_t N, const size_t R, typename Field::ConstElement_ptr A, const size_t lda, typename Field::Element_ptr T, const size_t ldt, const bool OnlyNonZeroVectors=false)
 Extracts a triangular matrix from a compact storage A=L of rank R. More...
 
template<class Field >
void getTriangular (const Field &F, const FFLAS::FFLAS_UPLO Uplo, const FFLAS::FFLAS_DIAG diag, const size_t M, const size_t N, const size_t R, typename Field::Element_ptr A, const size_t lda)
 Cleans up a compact storage A=L to reveal a triangular matrix of rank R. More...
 
template<class Field >
void getEchelonForm (const Field &F, const FFLAS::FFLAS_UPLO Uplo, const FFLAS::FFLAS_DIAG diag, const size_t M, const size_t N, const size_t R, const size_t *P, typename Field::ConstElement_ptr A, const size_t lda, typename Field::Element_ptr T, const size_t ldt, const bool OnlyNonZeroVectors=false, const FFPACK_LU_TAG LuTag=FfpackSlabRecursive)
 Extracts a matrix in echelon form from a compact storage A=L of rank R obtained by RowEchelonForm or ColumnEchelonForm. More...
 
template<class Field >
void getEchelonForm (const Field &F, const FFLAS::FFLAS_UPLO Uplo, const FFLAS::FFLAS_DIAG diag, const size_t M, const size_t N, const size_t R, const size_t *P, typename Field::Element_ptr A, const size_t lda, const FFPACK_LU_TAG LuTag=FfpackSlabRecursive)
 Cleans up a compact storage A=L obtained by RowEchelonForm or ColumnEchelonForm to reveal an echelon form of rank R. More...
 
template<class Field >
void getEchelonTransform (const Field &F, const FFLAS::FFLAS_UPLO Uplo, const FFLAS::FFLAS_DIAG diag, const size_t M, const size_t N, const size_t R, const size_t *P, const size_t *Q, typename Field::ConstElement_ptr A, const size_t lda, typename Field::Element_ptr T, const size_t ldt, const FFPACK_LU_TAG LuTag=FfpackSlabRecursive)
 Extracts a transformation matrix to echelon form from a compact storage A=L of rank R obtained by RowEchelonForm or ColumnEchelonForm. More...
 
template<class Field >
void getReducedEchelonForm (const Field &F, const FFLAS::FFLAS_UPLO Uplo, const size_t M, const size_t N, const size_t R, const size_t *P, typename Field::ConstElement_ptr A, const size_t lda, typename Field::Element_ptr T, const size_t ldt, const bool OnlyNonZeroVectors=false, const FFPACK_LU_TAG LuTag=FfpackSlabRecursive)
 Extracts a matrix in echelon form from a compact storage A=L of rank R obtained by ReducedRowEchelonForm or ReducedColumnEchelonForm with transform = true. More...
 
template<class Field >
void getReducedEchelonForm (const Field &F, const FFLAS::FFLAS_UPLO Uplo, const size_t M, const size_t N, const size_t R, const size_t *P, typename Field::Element_ptr A, const size_t lda, const FFPACK_LU_TAG LuTag=FfpackSlabRecursive)
 Cleans up a compact storage A=L of rank R obtained by ReducedRowEchelonForm or ReducedColumnEchelonForm with transform = true. More...
 
template<class Field >
void getReducedEchelonTransform (const Field &F, const FFLAS::FFLAS_UPLO Uplo, const size_t M, const size_t N, const size_t R, const size_t *P, const size_t *Q, typename Field::ConstElement_ptr A, const size_t lda, typename Field::Element_ptr T, const size_t ldt, const FFPACK_LU_TAG LuTag=FfpackSlabRecursive)
 Extracts a transformation matrix to echelon form from a compact storage A=L of rank R obtained by RowEchelonForm or ColumnEchelonForm. More...
 
void PLUQtoEchelonPermutation (const size_t N, const size_t R, const size_t *P, size_t *outPerm)
 Auxiliary routine: determines the permutation that changes a PLUQ decomposition into a echelon form revealing PLUQ decomposition.
 
template<class Field >
Field::Element_ptr LQUPtoInverseOfFullRankMinor (const Field &F, const size_t rank, typename Field::Element_ptr A_factors, const size_t lda, const size_t *QtPointer, typename Field::Element_ptr X, const size_t ldx)
 LQUPtoInverseOfFullRankMinor. More...
 
template<class Field >
Field::Element_ptr buildMatrix (const Field &F, typename Field::ConstElement_ptr E, typename Field::ConstElement_ptr C, const size_t lda, const size_t *B, const size_t *T, const size_t me, const size_t mc, const size_t lambda, const size_t mu)
 
template<class Field >
Field::Element * RandomMatrix (const Field &F, typename Field::Element *A, size_t m, size_t n, size_t lda, size_t b=0)
 Random Matrix. More...
 
size_t RandInt (size_t a, size_t b)
 Random integer in range. More...
 
template<class Field >
Field::Element_ptr RandomMatrixWithRank (const Field &F, typename Field::Element_ptr A, size_t lda, size_t r, size_t m, size_t n)
 Random Matrix with prescribed rank. More...
 
template<class Field >
void RandomMatrixWithRankandRandomRPM (const Field &F, typename Field::Element_ptr A, size_t lda, size_t R, size_t M, size_t N)
 Random Matrix with prescribed rank, with random rank profile matrix Creates an m x n matrix with random entries, rank r and with a rank profile matrix chosen uniformly at random. More...
 
template<class Field >
Field::Element * RandomMatrixWithDet (const Field &F, typename Field::Element *A, typename Field::Element d, size_t n, size_t lda)
 Random Matrix with prescribed det. More...
 
int RandInt (int a, int b)
 Random integer in range. More...
 

Detailed Description

Finite Field PACK Set of elimination based routines for dense linear algebra.

This namespace enlarges the set of BLAS routines of the class FFLAS, with higher level routines based on elimination.

Function Documentation

◆ applyP()

void applyP ( const Field &  F,
const FFLAS::FFLAS_SIDE  Side,
const FFLAS::FFLAS_TRANSPOSE  Trans,
const size_t  M,
const size_t  ibeg,
const size_t  iend,
typename Field::Element_ptr  A,
const size_t  lda,
const size_t *  P 
)

Apply a permutation P, stored in the LAPACK format (a sequence of transpositions) between indices ibeg and iend of P to (iend-ibeg) vectors of size M stored in A (as column for NoTrans and rows for Trans).

Side==FFLAS::FflasLeft for row permutation Side==FFLAS::FflasRight for a column permutation Trans==FFLAS::FflasTrans for the inverse permutation of P

Parameters
F
Side
Trans
M
ibeg
iend
A
lda
P
Warning
not sure the submatrix is still a permutation and the one we expect in all cases... examples for iend=2, ibeg=1 and P=[2,2,2]

◆ MonotonicApplyP()

void MonotonicApplyP ( const Field &  F,
const FFLAS::FFLAS_SIDE  Side,
const FFLAS::FFLAS_TRANSPOSE  Trans,
const size_t  M,
const size_t  ibeg,
const size_t  iend,
typename Field::Element_ptr  A,
const size_t  lda,
const size_t *  P,
const size_t  R 
)

Apply a R-monotonically increasing permutation P, to the matrix A.

MonotonicApplyP Apply a permutation defined by the first R entries of the vector P (the pivots).

The permutation represented by P is defined as follows:

  • the first R values of P is a LAPACK reprensentation (a sequence of transpositions)
  • the remaining iend-ibeg-R values of the permutation are in a monotonically increasing progression Side==FFLAS::FflasLeft for row permutation Side==FFLAS::FflasRight for a column permutation Trans==FFLAS::FflasTrans for the inverse permutation of P
    Parameters
    F
    Side
    Trans
    M
    ibeg
    iend
    A
    lda
    P
    RThe non pivot elements, are located in montonically increasing order.

◆ fgetrs() [1/2]

void fgetrs ( const Field &  F,
const FFLAS::FFLAS_SIDE  Side,
const size_t  M,
const size_t  N,
const size_t  R,
typename Field::Element_ptr  A,
const size_t  lda,
const size_t *  P,
const size_t *  Q,
typename Field::Element_ptr  B,
const size_t  ldb,
int *  info 
)

Solve the system $A X = B$ or $X A = B$.

Solving using the LQUP decomposition of A already computed inplace with LUdivine(FFLAS::FflasNoTrans, FFLAS::FflasNonUnit). Version for A square. If A is rank deficient, a solution is returned if the system is consistent, Otherwise an info is 1

Parameters
Ffield
SideDetermine wheter the resolution is left or right looking.
Mrow dimension of B
Ncol dimension of B
Rrank of A
Ainput matrix
ldaleading dimension of A
Pcolumn permutation of the LQUP decomposition of A
Qcolumn permutation of the LQUP decomposition of A
BRight/Left hand side matrix. Initially stores B, finally stores the solution X.
ldbleading dimension of B
infoSuccess of the computation: 0 if successfull, >0 if system is inconsistent

◆ fgetrs() [2/2]

Field::Element_ptr fgetrs ( const Field &  F,
const FFLAS::FFLAS_SIDE  Side,
const size_t  M,
const size_t  N,
const size_t  NRHS,
const size_t  R,
typename Field::Element_ptr  A,
const size_t  lda,
const size_t *  P,
const size_t *  Q,
typename Field::Element_ptr  X,
const size_t  ldx,
typename Field::ConstElement_ptr  B,
const size_t  ldb,
int *  info 
)

Solve the system A X = B or X A = B.

Solving using the LQUP decomposition of A already computed inplace with LUdivine(FFLAS::FflasNoTrans, FFLAS::FflasNonUnit). Version for A rectangular. If A is rank deficient, a solution is returned if the system is consistent, Otherwise an info is 1

Parameters
Ffield
SideDetermine wheter the resolution is left or right looking.
Mrow dimension of A
Ncol dimension of A
NRHSnumber of columns (if Side = FFLAS::FflasLeft) or row (if Side = FFLAS::FflasRight) of the matrices X and B
Rrank of A
Ainput matrix
ldaleading dimension of A
Pcolumn permutation of the LQUP decomposition of A
Qcolumn permutation of the LQUP decomposition of A
Xsolution matrix
ldxleading dimension of X
BRight/Left hand side matrix.
ldbleading dimension of B
infoSucces of the computation: 0 if successfull, >0 if system is inconsistent

◆ fgesv() [1/2]

size_t fgesv ( const Field &  F,
const FFLAS::FFLAS_SIDE  Side,
const size_t  M,
const size_t  N,
typename Field::Element_ptr  A,
const size_t  lda,
typename Field::Element_ptr  B,
const size_t  ldb,
int *  info 
)

Square system solver.

Parameters
FThe computation domain
SideDetermine wheter the resolution is left or right looking
Mrow dimension of B
Ncol dimension of B
Ainput matrix
ldaleading dimension of A
BRight/Left hand side matrix. Initially contains B, finally contains the solution X.
ldbleading dimension of B
infoSuccess of the computation: 0 if successfull, >0 if system is inconsistent
Returns
the rank of the system

Solve the system A X = B or X A = B. Version for A square. If A is rank deficient, a solution is returned if the system is consistent, Otherwise an info is 1

◆ fgesv() [2/2]

size_t fgesv ( const Field &  F,
const FFLAS::FFLAS_SIDE  Side,
const size_t  M,
const size_t  N,
const size_t  NRHS,
typename Field::Element_ptr  A,
const size_t  lda,
typename Field::Element_ptr  X,
const size_t  ldx,
typename Field::ConstElement_ptr  B,
const size_t  ldb,
int *  info 
)

Rectangular system solver.

Parameters
FThe computation domain
SideDetermine wheter the resolution is left or right looking
Mrow dimension of A
Ncol dimension of A
NRHSnumber of columns (if Side = FFLAS::FflasLeft) or row (if Side = FFLAS::FflasRight) of the matrices X and B
Ainput matrix
ldaleading dimension of A
BRight/Left hand side matrix. Initially contains B, finally contains the solution X.
ldbleading dimension of B
X
ldx
infoSuccess of the computation: 0 if successfull, >0 if system is inconsistent
Returns
the rank of the system

Solve the system A X = B or X A = B. Version for A square. If A is rank deficient, a solution is returned if the system is consistent, Otherwise an info is 1

◆ ftrtri()

void ftrtri ( const Field &  F,
const FFLAS::FFLAS_UPLO  Uplo,
const FFLAS::FFLAS_DIAG  Diag,
const size_t  N,
typename Field::Element_ptr  A,
const size_t  lda 
)

Compute the inverse of a triangular matrix.

Parameters
F
Uplowhether the matrix is upper of lower triangular
Diagwhether the matrix if unit diagonal
N
A
lda

◆ ftrtrm()

void ftrtrm ( const Field &  F,
const FFLAS::FFLAS_DIAG  diag,
const size_t  N,
typename Field::Element_ptr  A,
const size_t  lda 
)

Compute the product UL.

Product UL of the upper, resp lower triangular matrices U and L stored one above the other in the square matrix A. Diag == Unit if the matrix U is unit diagonal

Parameters
F
diag
N
A
lda

◆ PLUQ()

size_t PLUQ ( const Field &  F,
const FFLAS::FFLAS_DIAG  Diag,
const size_t  M,
const size_t  N,
typename Field::Element_ptr  A,
const size_t  lda,
size_t *  P,
size_t *  Q 
)
inline

Compute the PLUQ factorization of the given matrix.

Using a block algorithm and return its rank. The permutations P and Q are represented using LAPACK's convention.

Parameters
Ffield
Diagwhether U should have a unit diagonal or not
trans

◆ LUdivine()

size_t LUdivine ( const Field &  F,
const FFLAS::FFLAS_DIAG  Diag,
const FFLAS::FFLAS_TRANSPOSE  trans,
const size_t  M,
const size_t  N,
typename Field::Element_ptr  A,
const size_t  lda,
size_t *  P,
size_t *  Qt,
const FFPACK_LU_TAG  LuTag = FfpackSlabRecursive,
const size_t  cutoff = 0 
)
inline

Compute the CUP factorization of the given matrix.

Using a block algorithm and return its rank. The permutations P and Q are represented using LAPACK's convention.

Parameters
Ffield
Diagwhether U should have a unit diagonal or not
transLU of $A^t$
Mmatrix row dimension
Nmatrix column dimension
Ainput matrix
ldaleading dimension of A
Pthe column permutation
Qtthe transpose of the row permutation Q
LuTagflag for setting the earling termination if the matrix is singular
cutoffUNKOWN TAG, probably a switch to a faster algo below cutoff
Returns
the rank of A
Bibliography:
  • Jeannerod C-P, Pernet, C. and Storjohann, A. Rank-profile revealing Gaussian elimination and the CUP matrix decomposition , J. of Symbolic Comp., 2013
  • Pernet C, Brassel M LUdivine, une divine factorisation LU, 2002
Todo:
std::swap ?
Todo:
std::swap ?

◆ ColumnEchelonForm()

size_t ColumnEchelonForm ( const Field &  F,
const size_t  M,
const size_t  N,
typename Field::Element_ptr  A,
const size_t  lda,
size_t *  P,
size_t *  Qt,
bool  transform = false,
const FFPACK_LU_TAG  LuTag = FfpackSlabRecursive 
)
inline

Compute the Column Echelon form of the input matrix in-place.

If LuTag == FfpackTileRecursive, then after the computation A = [ M \ V ] such that AU = C is a column echelon decomposition of A, with U = P^T [ V ] and C = M + Q [ Ir ] [ 0 In-r ] [ 0 ] If LuTag == FfpackTileRecursive then A = [ N \ V ] such that the same holds with M = Q N

Qt = Q^T If transform=false, the matrix V is not computed. See also test-colechelon for an example of use

Parameters
F
M
N
A
lda
Pthe column permutation
Qtthe row position of the pivots in the echelon form
transform

◆ RowEchelonForm()

size_t RowEchelonForm ( const Field &  F,
const size_t  M,
const size_t  N,
typename Field::Element_ptr  A,
const size_t  lda,
size_t *  P,
size_t *  Qt,
const bool  transform = false,
const FFPACK_LU_TAG  LuTag = FfpackSlabRecursive 
)
inline

Compute the Row Echelon form of the input matrix in-place.

If LuTag == FfpackTileRecursive, then after the computation A = [ L \ M ] such that X A = R is a row echelon decomposition of A, with X = [ L 0 ] P and R = M + [Ir 0] Q^T [ In-r] If LuTag == FfpackTileRecursive then A = [ L \ N ] such that the same holds with M = N Q^T Qt = Q^T If transform=false, the matrix L is not computed. See also test-rowechelon for an example of use

Parameters
F
M
N
A
lda
Pthe row permutation
Qtthe column position of the pivots in the echelon form
transform

◆ ReducedColumnEchelonForm()

size_t ReducedColumnEchelonForm ( const Field &  F,
const size_t  M,
const size_t  N,
typename Field::Element_ptr  A,
const size_t  lda,
size_t *  P,
size_t *  Qt,
const bool  transform = false,
const FFPACK_LU_TAG  LuTag = FfpackSlabRecursive 
)
inline

Compute the Reduced Column Echelon form of the input matrix in-place.

After the computation A = [ V ] such that AX = R is a reduced col echelon [ M 0 ] decomposition of A, where X = P^T [ V ] and R = Q [ Ir ] [ 0 In-r ] [ M 0 ] Qt = Q^T If transform=false, the matrix X is not computed and the matrix A = R

Parameters
F
M
N
A
lda
P
Qt
transform

◆ ReducedRowEchelonForm()

size_t ReducedRowEchelonForm ( const Field &  F,
const size_t  M,
const size_t  N,
typename Field::Element_ptr  A,
const size_t  lda,
size_t *  P,
size_t *  Qt,
const bool  transform = false,
const FFPACK_LU_TAG  LuTag = FfpackSlabRecursive 
)
inline

Compute the Reduced Row Echelon form of the input matrix in-place.

After the computation A = [ V1 M ] such that X A = R is a reduced row echelon [ V2 0 ] decomposition of A, where X = [ V1 0 ] P and R = [ Ir M ] Q^T [ V2 In-r ] [ 0 ] Qt = Q^T If transform=false, the matrix X is not computed and the matrix A = R

Parameters
F
M
N
A
lda
P
Qt
transform

◆ ReducedRowEchelonForm2()

size_t ReducedRowEchelonForm2 ( const Field &  F,
const size_t  M,
const size_t  N,
typename Field::Element_ptr  A,
const size_t  lda,
size_t *  P,
size_t *  Qt,
const bool  transform = true 
)
inline

Variant by the block recursive algorithm.

(See A. Storjohann Thesis 2000) !!!!!! Warning !!!!!! This code is NOT WORKING properly for some echelon structures. This is due to a limitation of the way we represent permutation matrices (LAPACK's standard):

  • a composition of transpositions Tij of the form P = T_{1,j1} o T_{2,j2] o...oT_{r,jr}, with jk>k for all 0 < k <= r <= n
  • The permutation on the columns, performed by this block recursive algorithm cannot be represented with such a composition. Consequently this function should only be used for benchmarks

◆ REF()

size_t REF ( const Field &  F,
const size_t  M,
const size_t  N,
typename Field::Element_ptr  A,
const size_t  lda,
const size_t  colbeg,
const size_t  rowbeg,
const size_t  colsize,
size_t *  Qt,
size_t *  P 
)
inline

REF.


| I | A11 | A12 | | |-—|–—|–—|-—| | |I | *| A22 | | | |0 | 0| A22 | | |-—|–—|–—|-—| | | 0 | A32 | | |-—|–—|–—|-—|

where the transformation matrix is stored at the pivot column position

Bug:
safe ???

◆ Invert() [1/2]

Field::Element_ptr Invert ( const Field &  F,
const size_t  M,
typename Field::Element_ptr  A,
const size_t  lda,
int &  nullity 
)

Invert the given matrix in place or computes its nullity if it is singular.

An inplace $2n^3$ algorithm is used.

Parameters
FThe computation domain
Morder of the matrix
[in,out]Ainput matrix ( $M \times M$)
ldaleading dimension of A
nullitydimension of the kernel of A
Returns
pointer to $A$ and $A \gets A^{-1}$

◆ Invert() [2/2]

Field::Element_ptr Invert ( const Field &  F,
const size_t  M,
typename Field::ConstElement_ptr  A,
const size_t  lda,
typename Field::Element_ptr  X,
const size_t  ldx,
int &  nullity 
)

Invert the given matrix in place or computes its nullity if it is singular.

Precondition
X is preallocated and should be large enough to store the $ m \times m$ matrix A.
Parameters
FThe computation domain
Morder of the matrix
[in]Ainput matrix ( $M \times M$)
ldaleading dimension of A
[out]Xthis is the inverse of A if A is invertible (non NULL and $ \mathtt{nullity} = 0$). It is untouched otherwise.
ldxleading dimension of X
nullitydimension of the kernel of A
Returns
pointer to $X = A^{-1}$

◆ Invert2()

Field::Element_ptr Invert2 ( const Field &  F,
const size_t  M,
typename Field::Element_ptr  A,
const size_t  lda,
typename Field::Element_ptr  X,
const size_t  ldx,
int &  nullity 
)

Invert the given matrix or computes its nullity if it is singular.

An $2n^3f$ algorithm is used. This routine can be % faster than FFPACK::Invert but is not totally inplace.

Precondition
X is preallocated and should be large enough to store the $ m \times m$ matrix A.
Warning
A is overwritten here !
Bug:
not tested.
Parameters
F
Morder of the matrix
[in,out]Ainput matrix ( $M \times M$). On output, A is modified and represents a "psycological" factorisation LU.
ldaleading dimension of A
[out]Xthis is the inverse of A if A is invertible (non NULL and $ \mathtt{nullity} = 0$). It is untouched otherwise.
ldxleading dimension of X
nullitydimension of the kernel of A
Returns
pointer to $X = A^{-1}$
Todo:
this init is not all necessary (done after ftrtri)
Todo:
this init is not all necessary (done after ftrtri)

◆ CharpolyArithProg()

std::list< Polynomial > & CharpolyArithProg ( const Field &  F,
std::list< Polynomial > &  frobeniusForm,
const size_t  N,
typename Field::Element_ptr  A,
const size_t  lda,
const size_t  c 
)
Todo:
swap to save space ??

◆ MinPoly()

Polynomial & MinPoly ( const Field &  F,
Polynomial &  minP,
const size_t  N,
typename Field::ConstElement_ptr  A,
const size_t  lda,
typename Field::Element_ptr  X,
const size_t  ldx,
size_t *  P,
const FFPACK_MINPOLY_TAG  MinTag = FFPACK::FfpackDense,
const size_t  kg_mc = 0,
const size_t  kg_mb = 0,
const size_t  kg_j = 0 
)

Compute the minimal polynomial.

Minpoly of (A,v) using an LUP factorization of the Krylov Base (v, Av, .., A^kv) U,X must be (n+1)*n U contains the Krylov matrix and X, its LSP factorization

◆ Rank()

size_t Rank ( const Field &  F,
const size_t  M,
const size_t  N,
typename Field::Element_ptr  A,
const size_t  lda 
)

Computes the rank of the given matrix using a LQUP factorization.

The input matrix is modified.

Parameters
Ffield
Mrow dimension of the matrix
Ncolumn dimension of the matrix
Ainput matrix
ldaleading dimension of A

◆ IsSingular()

bool IsSingular ( const Field &  F,
const size_t  M,
const size_t  N,
typename Field::Element_ptr  A,
const size_t  lda 
)

Returns true if the given matrix is singular.

The method is a block elimination with early termination

using LQUP factorization with early termination. If M != N, then the matrix is virtually padded with zeros to make it square and it's determinant is zero.

Warning
The input matrix is modified.
Parameters
Ffield
Mrow dimension of the matrix
Ncolumn dimension of the matrix.
[in,out]Ainput matrix
ldaleading dimension of A

◆ Det()

Field::Element Det ( const Field &  F,
const size_t  M,
const size_t  N,
typename Field::Element_ptr  A,
const size_t  lda 
)

Returns the determinant of the given matrix.

The method is a block elimination with early termination using LQUP factorization with early termination. If M != N, then the matrix is virtually padded with zeros to make it square and it's determinant is zero.

Warning
The input matrix is modified.
Parameters
Ffield
Mrow dimension of the matrix
Ncolumn dimension of the matrix.
[in,out]Ainput matrix
ldaleading dimension of A

◆ solveLB()

void solveLB ( const Field &  F,
const FFLAS::FFLAS_SIDE  Side,
const size_t  M,
const size_t  N,
const size_t  R,
typename Field::Element_ptr  L,
const size_t  ldl,
const size_t *  Q,
typename Field::Element_ptr  B,
const size_t  ldb 
)

Solve L X = B or X L = B in place.

L is M*M if Side == FFLAS::FflasLeft and N*N if Side == FFLAS::FflasRight, B is M*N. Only the R non trivial column of L are stored in the M*R matrix L Requirement : so that L could be expanded in-place

◆ solveLB2()

void solveLB2 ( const Field &  F,
const FFLAS::FFLAS_SIDE  Side,
const size_t  M,
const size_t  N,
const size_t  R,
typename Field::Element_ptr  L,
const size_t  ldl,
const size_t *  Q,
typename Field::Element_ptr  B,
const size_t  ldb 
)

Solve L X = B in place.

L is M*M or N*N, B is M*N. Only the R non trivial column of L are stored in the M*R matrix L

◆ RandomNullSpaceVector()

void RandomNullSpaceVector ( const Field &  F,
const FFLAS::FFLAS_SIDE  Side,
const size_t  M,
const size_t  N,
typename Field::Element_ptr  A,
const size_t  lda,
typename Field::Element_ptr  X,
const size_t  incX 
)

Computes a vector of the Left/Right nullspace of the matrix A.

Parameters
FThe computation domain
Side
M
N
[in,out]Ainput matrix of dimension M x N, A is modified to its LU version
lda
[out]Xoutput vector
incX

◆ NullSpaceBasis()

size_t NullSpaceBasis ( const Field &  F,
const FFLAS::FFLAS_SIDE  Side,
const size_t  M,
const size_t  N,
typename Field::Element_ptr  A,
const size_t  lda,
typename Field::Element_ptr &  NS,
size_t &  ldn,
size_t &  NSdim 
)

Computes a basis of the Left/Right nullspace of the matrix A.

return the dimension of the nullspace.

Parameters
FThe computation domain
Side
M
N
[in,out]Ainput matrix of dimension M x N, A is modified
lda
[out]NSoutput matrix of dimension N x NSdim (allocated here)
[out]ldn
[out]NSdimthe dimension of the Nullspace (N-rank(A))

◆ RowRankProfile()

size_t RowRankProfile ( const Field &  F,
const size_t  M,
const size_t  N,
typename Field::Element_ptr  A,
const size_t  lda,
size_t *&  rkprofile,
const FFPACK_LU_TAG  LuTag = FfpackSlabRecursive 
)
inline

Computes the row rank profile of A.

Parameters
F
M
N
Ainput matrix of dimension M x N
lda
rkprofilereturn the rank profile as an array of row indexes, of dimension r=rank(A)
LuTagchooses the elimination algorithm. SlabRecursive for LUdivine, TileRecursive for PLUQ

A is modified rkprofile is allocated during the computation.

Returns
R

◆ ColumnRankProfile()

size_t ColumnRankProfile ( const Field &  F,
const size_t  M,
const size_t  N,
typename Field::Element_ptr  A,
const size_t  lda,
size_t *&  rkprofile,
const FFPACK_LU_TAG  LuTag = FfpackSlabRecursive 
)
inline

Computes the column rank profile of A.

Parameters
F
M
N
Ainput matrix of dimension
lda
rkprofilereturn the rank profile as an array of row indexes, of dimension r=rank(A)
LuTagchooses the elimination algorithm. SlabRecursive for LUdivine, TileRecursive for PLUQ

A is modified rkprofile is allocated during the computation.

Returns
R

◆ RankProfileFromLU()

void RankProfileFromLU ( const size_t *  P,
const size_t  N,
const size_t  R,
size_t *  rkprofile,
const FFPACK_LU_TAG  LuTag 
)
inline

Recovers the column/row rank profile from the permutation of an LU decomposition.

Works with both the CUP/PLE decompositions (obtained by LUdivine) or the PLUQ decomposition Assumes that the output vector containing the rank profile is already allocated.

Parameters
Pthe permutation carrying the rank profile information
Nthe row/col dimension for a row/column rank profile
Rthe rank of the matrix (
rkprofilereturn the rank profile as an array of indices
LuTagchooses the elimination algorithm. SlabRecursive for LUdivine, TileRecursive for PLUQ

A is modified

◆ LeadingSubmatrixRankProfiles()

size_t LeadingSubmatrixRankProfiles ( const size_t  M,
const size_t  N,
const size_t  R,
const size_t  LSm,
const size_t  LSn,
const size_t *  P,
const size_t *  Q,
size_t *  RRP,
size_t *  CRP 
)
inline

Recovers the row and column rank profiles of any leading submatrix from the PLUQ decomposition.

Only works with the PLUQ decomposition Assumes that the output vectors containing the rank profiles are already allocated.

Parameters
Pthe permutation carrying the rank profile information
Mthe row dimension of the initial matrix
Nthe column dimension of the initial matrix
Rthe rank of the initial matrix
LSmthe row dimension of the leading submatrix considered
LSnthe column dimension of the leading submatrix considered
Pthe row permutation of the PLUQ decomposition
Qthe column permutation of the PLUQ decomposition
RRPreturn the row rank profile of the leading
LuTagchooses the elimination algorithm. SlabRecursive for LUdivine, TileRecursive for PLUQ
Returns
the rank of the LSm x LSn leading submatrix

A is modified

Bibliography:
  • Dumas J-G., Pernet C., and Sultan Z. Simultaneous computation of the row and column rank profiles , ISSAC'13.

◆ RowRankProfileSubmatrixIndices()

size_t RowRankProfileSubmatrixIndices ( const Field &  F,
const size_t  M,
const size_t  N,
typename Field::Element_ptr  A,
const size_t  lda,
size_t *&  rowindices,
size_t *&  colindices,
size_t &  R 
)

RowRankProfileSubmatrixIndices.

Computes the indices of the submatrix r*r X of A whose rows correspond to the row rank profile of A.

Parameters
F
M
N
Ainput matrix of dimension
rowindicesarray of the row indices of X in A
colindicesarray of the col indices of X in A
lda
[out]Rrowindices and colindices are allocated during the computation. A is modified
Returns
R

◆ ColRankProfileSubmatrixIndices()

size_t ColRankProfileSubmatrixIndices ( const Field &  F,
const size_t  M,
const size_t  N,
typename Field::Element_ptr  A,
const size_t  lda,
size_t *&  rowindices,
size_t *&  colindices,
size_t &  R 
)

Computes the indices of the submatrix r*r X of A whose columns correspond to the column rank profile of A.

Parameters
F
M
N
Ainput matrix of dimension
rowindicesarray of the row indices of X in A
colindicesarray of the col indices of X in A
lda
[out]Rrowindices and colindices are allocated during the computation.
Warning
A is modified
Returns
R

◆ RowRankProfileSubmatrix()

size_t RowRankProfileSubmatrix ( const Field &  F,
const size_t  M,
const size_t  N,
typename Field::Element_ptr  A,
const size_t  lda,
typename Field::Element_ptr &  X,
size_t &  R 
)

Computes the r*r submatrix X of A, by picking the row rank profile rows of A.

Parameters
F
M
N
Ainput matrix of dimension M x N
lda
Xthe output matrix
[out]RA is not modified X is allocated during the computation.
Returns
R

◆ ColRankProfileSubmatrix()

size_t ColRankProfileSubmatrix ( const Field &  F,
const size_t  M,
const size_t  N,
typename Field::Element_ptr  A,
const size_t  lda,
typename Field::Element_ptr &  X,
size_t &  R 
)

Compute the $ r\times r$ submatrix X of A, by picking the row rank profile rows of A.

Parameters
F
M
N
Ainput matrix of dimension M x N
lda
Xthe output matrix
[out]RA is not modified X is allocated during the computation.
Returns
R

◆ getTriangular() [1/2]

void getTriangular ( const Field &  F,
const FFLAS::FFLAS_UPLO  Uplo,
const FFLAS::FFLAS_DIAG  diag,
const size_t  M,
const size_t  N,
const size_t  R,
typename Field::ConstElement_ptr  A,
const size_t  lda,
typename Field::Element_ptr  T,
const size_t  ldt,
const bool  OnlyNonZeroVectors = false 
)
inline

Extracts a triangular matrix from a compact storage A=L of rank R.

if OnlyNonZeroVectors is false, then T and A have the same dimensions Otherwise, T is R x N if UpLo = FflasUpper, else T is M x R

Parameters
Fbase field
UpLoselects if the upper or lower triangular matrix is returned
diagselects if the triangular matrix unit-diagonal
Mrow dimension of T
Ncolumn dimension of T
Rrank of the triangular matrix (how many rows/columns need to be copied)
Ainput matrix
ldaleading dimension of A
Toutput matrix
ldtleading dimension of T
OnlyNonZeroVectorsdecides whether the last zero rows/columns should be ignored
Todo:
just one triangular fzero+fassign ?
Todo:
just one triangular fzero+fassign ?

◆ getTriangular() [2/2]

void getTriangular ( const Field &  F,
const FFLAS::FFLAS_UPLO  Uplo,
const FFLAS::FFLAS_DIAG  diag,
const size_t  M,
const size_t  N,
const size_t  R,
typename Field::Element_ptr  A,
const size_t  lda 
)
inline

Cleans up a compact storage A=L to reveal a triangular matrix of rank R.

Parameters
Fbase field
UpLoselects if the upper or lower triangular matrix is revealed
diagselects if the triangular matrix unit-diagonal
Mrow dimension of A
Ncolumn dimension of A
Rrank of the triangular matrix
Ainput/output matrix
ldaleading dimension of A
Todo:
just one triangular fzero+fassign ?
Todo:
just one triangular fzero+fassign ?

◆ getEchelonForm() [1/2]

void getEchelonForm ( const Field &  F,
const FFLAS::FFLAS_UPLO  Uplo,
const FFLAS::FFLAS_DIAG  diag,
const size_t  M,
const size_t  N,
const size_t  R,
const size_t *  P,
typename Field::ConstElement_ptr  A,
const size_t  lda,
typename Field::Element_ptr  T,
const size_t  ldt,
const bool  OnlyNonZeroVectors = false,
const FFPACK_LU_TAG  LuTag = FfpackSlabRecursive 
)
inline

Extracts a matrix in echelon form from a compact storage A=L of rank R obtained by RowEchelonForm or ColumnEchelonForm.

Either L or U is in Echelon form (depending on Uplo) The echelon structure is defined by the first R values of the array P. row and column dimension of T are greater or equal to that of A

Parameters
Fbase field
UpLoselects if the upper or lower triangular matrix is returned
diagselects if the echelon matrix has unit pivots
Mrow dimension of T
Ncolumn dimension of T
Rrank of the triangular matrix (how many rows/columns need to be copied)
Ppositions of the R pivots
Ainput matrix
ldaleading dimension of A
Toutput matrix
ldtleading dimension of T
OnlyNonZeroVectorsdecides whether the last zero rows/columns should be ignored
LuTagwhich factorized form (CUP/PLE if FfpackSlabRecursive, PLUQ if FfpackTileRecursive)

◆ getEchelonForm() [2/2]

void getEchelonForm ( const Field &  F,
const FFLAS::FFLAS_UPLO  Uplo,
const FFLAS::FFLAS_DIAG  diag,
const size_t  M,
const size_t  N,
const size_t  R,
const size_t *  P,
typename Field::Element_ptr  A,
const size_t  lda,
const FFPACK_LU_TAG  LuTag = FfpackSlabRecursive 
)
inline

Cleans up a compact storage A=L obtained by RowEchelonForm or ColumnEchelonForm to reveal an echelon form of rank R.

Either L or U is in Echelon form (depending on Uplo) The echelon structure is defined by the first R values of the array P.

Parameters
Fbase field
UpLoselects if the upper or lower triangular matrix is returned
diagselects if the echelon matrix has unit pivots
Mrow dimension of A
Ncolumn dimension of A
Rrank of the triangular matrix (how many rows/columns need to be copied)
Ppositions of the R pivots
Ainput/output matrix
ldaleading dimension of A
LuTagwhich factorized form (CUP/PLE if FfpackSlabRecursive, PLUQ if FfpackTileRecursive)

◆ getEchelonTransform()

void getEchelonTransform ( const Field &  F,
const FFLAS::FFLAS_UPLO  Uplo,
const FFLAS::FFLAS_DIAG  diag,
const size_t  M,
const size_t  N,
const size_t  R,
const size_t *  P,
const size_t *  Q,
typename Field::ConstElement_ptr  A,
const size_t  lda,
typename Field::Element_ptr  T,
const size_t  ldt,
const FFPACK_LU_TAG  LuTag = FfpackSlabRecursive 
)
inline

Extracts a transformation matrix to echelon form from a compact storage A=L of rank R obtained by RowEchelonForm or ColumnEchelonForm.

If Uplo == FflasLower: T is N x N (already allocated) such that A T = C is a transformation of A in Column echelon form Else T is M x M (already allocated) such that T A = E is a transformation of A in Row Echelon form

Parameters
Fbase field
UpLoLower means Transformation to Column Echelon Form, Upper, to Row Echelon Form
diagselects if the echelon matrix has unit pivots
Mrow dimension of A
Ncolumn dimension of A
Rrank of the triangular matrix
Ppermutation matrix
Ainput matrix
ldaleading dimension of A
Toutput matrix
ldtleading dimension of T
LuTagwhich factorized form (CUP/PLE if FfpackSlabRecursive, PLUQ if FfpackTileRecursive)

◆ getReducedEchelonForm() [1/2]

void getReducedEchelonForm ( const Field &  F,
const FFLAS::FFLAS_UPLO  Uplo,
const size_t  M,
const size_t  N,
const size_t  R,
const size_t *  P,
typename Field::ConstElement_ptr  A,
const size_t  lda,
typename Field::Element_ptr  T,
const size_t  ldt,
const bool  OnlyNonZeroVectors = false,
const FFPACK_LU_TAG  LuTag = FfpackSlabRecursive 
)
inline

Extracts a matrix in echelon form from a compact storage A=L of rank R obtained by ReducedRowEchelonForm or ReducedColumnEchelonForm with transform = true.

Either L or U is in Echelon form (depending on Uplo) The echelon structure is defined by the first R values of the array P. row and column dimension of T are greater or equal to that of A

Parameters
Fbase field
UpLoselects if the upper or lower triangular matrix is returned
diagselects if the echelon matrix has unit pivots
Mrow dimension of T
Ncolumn dimension of T
Rrank of the triangular matrix (how many rows/columns need to be copied)
Ppositions of the R pivots
Ainput matrix
ldaleading dimension of A
ldtleading dimension of T
LuTagwhich factorized form (CUP/PLE if FfpackSlabRecursive, PLUQ if FfpackTileRecursive)
OnlyNonZeroVectorsdecides whether the last zero rows/columns should be ignored

◆ getReducedEchelonForm() [2/2]

void getReducedEchelonForm ( const Field &  F,
const FFLAS::FFLAS_UPLO  Uplo,
const size_t  M,
const size_t  N,
const size_t  R,
const size_t *  P,
typename Field::Element_ptr  A,
const size_t  lda,
const FFPACK_LU_TAG  LuTag = FfpackSlabRecursive 
)
inline

Cleans up a compact storage A=L of rank R obtained by ReducedRowEchelonForm or ReducedColumnEchelonForm with transform = true.

Either L or U is in Echelon form (depending on Uplo) The echelon structure is defined by the first R values of the array P.

Parameters
Fbase field
UpLoselects if the upper or lower triangular matrix is returned
diagselects if the echelon matrix has unit pivots
Mrow dimension of A
Ncolumn dimension of A
Rrank of the triangular matrix (how many rows/columns need to be copied)
Ppositions of the R pivots
Ainput/output matrix
ldaleading dimension of A
LuTagwhich factorized form (CUP/PLE if FfpackSlabRecursive, PLUQ if FfpackTileRecursive)

◆ getReducedEchelonTransform()

void getReducedEchelonTransform ( const Field &  F,
const FFLAS::FFLAS_UPLO  Uplo,
const size_t  M,
const size_t  N,
const size_t  R,
const size_t *  P,
const size_t *  Q,
typename Field::ConstElement_ptr  A,
const size_t  lda,
typename Field::Element_ptr  T,
const size_t  ldt,
const FFPACK_LU_TAG  LuTag = FfpackSlabRecursive 
)
inline

Extracts a transformation matrix to echelon form from a compact storage A=L of rank R obtained by RowEchelonForm or ColumnEchelonForm.

If Uplo == FflasLower: T is N x N (already allocated) such that A T = C is a transformation of A in Column echelon form Else T is M x M (already allocated) such that T A = E is a transformation of A in Row Echelon form

Parameters
Fbase field
UpLoselects Col or Row Echelon Form
diagselects if the echelon matrix has unit pivots
Mrow dimension of A
Ncolumn dimension of A
Rrank of the triangular matrix
Ppermutation matrix
Ainput matrix
ldaleading dimension of A
Toutput matrix
ldtleading dimension of T
LuTagwhich factorized form (CUP/PLE if FfpackSlabRecursive, PLUQ if FfpackTileRecursive)

◆ LQUPtoInverseOfFullRankMinor()

Field::Element_ptr LQUPtoInverseOfFullRankMinor ( const Field &  F,
const size_t  rank,
typename Field::Element_ptr  A_factors,
const size_t  lda,
const size_t *  QtPointer,
typename Field::Element_ptr  X,
const size_t  ldx 
)

LQUPtoInverseOfFullRankMinor.

Suppose A has been factorized as L.Q.U.P, with rank r. Then Qt.A.Pt has an invertible leading principal r x r submatrix This procedure efficiently computes the inverse of this minor and puts it into X.

Note
It changes the lower entries of A_factors in the process (NB: unless A was nonsingular and square)
Parameters
F
rankrank of the matrix.
A_factorsmatrix containing the L and U entries of the factorization
lda
QtPointertheLQUP->getQ()->getPointer() (note: getQ returns Qt!)
Xdesired location for output
ldx

◆ buildMatrix()

Field::Element_ptr FFPACK::buildMatrix ( const Field &  F,
typename Field::ConstElement_ptr  E,
typename Field::ConstElement_ptr  C,
const size_t  lda,
const size_t *  B,
const size_t *  T,
const size_t  me,
const size_t  mc,
const size_t  lambda,
const size_t  mu 
)
Bug:
is this :

◆ RandomMatrix()

Field::Element* FFPACK::RandomMatrix ( const Field &  F,
typename Field::Element *  A,
size_t  m,
size_t  n,
size_t  lda,
size_t  b = 0 
)

Random Matrix.

Creates a m x n matrix with random entries.

Parameters
Ffield
Apointer to the matrix (preallocated to at least m x lda field elements)
mnumber of rows in A
nnumber of cols in A
ldaleading dimension of A
Returns
pointer to A.

◆ RandInt() [1/2]

size_t FFPACK::RandInt ( size_t  a,
size_t  b 
)

Random integer in range.

Parameters
amin bound
bmax bound
Returns
a random integer in [a,b[

◆ RandomMatrixWithRank()

Field::Element_ptr FFPACK::RandomMatrixWithRank ( const Field &  F,
typename Field::Element_ptr  A,
size_t  lda,
size_t  r,
size_t  m,
size_t  n 
)

Random Matrix with prescribed rank.

Creates an m x n matrix with random entries and rank r.

Parameters
Ffield
Apointer to the matrix (preallocated to at least m x lda field elements)
rrank of the matrix to build
mnumber of rows in A
nnumber of cols in A
ldaleading dimension of A
Returns
pointer to A.
Todo:
compute LU with ftrtr

◆ RandomMatrixWithRankandRandomRPM()

void FFPACK::RandomMatrixWithRankandRandomRPM ( const Field &  F,
typename Field::Element_ptr  A,
size_t  lda,
size_t  R,
size_t  M,
size_t  N 
)

Random Matrix with prescribed rank, with random rank profile matrix Creates an m x n matrix with random entries, rank r and with a rank profile matrix chosen uniformly at random.

Parameters
Ffield
Apointer to the matrix (preallocated to at least m x lda field elements)
rrank of the matrix to build
mnumber of rows in A
nnumber of cols in A
ldaleading dimension of A
Returns
pointer to A.

◆ RandomMatrixWithDet()

Field::Element* FFPACK::RandomMatrixWithDet ( const Field &  F,
typename Field::Element *  A,
typename Field::Element  d,
size_t  n,
size_t  lda 
)

Random Matrix with prescribed det.

Bug:
duplicate with linbox Creates a m x n matrix with random entries and rank r.
Parameters
Ffield
Apointer to the matrix (preallocated to at least m x lda field elements)
rrank of the matrix to build
mnumber of rows in A
nnumber of cols in A
ldaleading dimension of A
Returns
pointer to A.
Todo:
compute LU with ftrtr

◆ RandInt() [2/2]

int FFPACK::RandInt ( int  a,
int  b 
)

Random integer in range.

Parameters
amin bound
bmax bound
Returns
a random integer in [a,b[