Set of elimination based routines for dense linear algebra. More...
#include "givaro/givpoly1.h"#include <fflas-ffpack/fflas-ffpack-config.h>#include "fflas-ffpack/fflas/fflas.h"#include <list>#include <vector>#include <iostream>#include <algorithm>#include "fflas-ffpack/checkers/checkers_ffpack.h"#include "ffpack_fgesv.inl"#include "ffpack_fgetrs.inl"#include "ffpack_fsytrf.inl"#include "fflas-ffpack/checkers/checkers_ffpack.inl"#include "ffpack_pluq.inl"#include "ffpack_pluq_mp.inl"#include "ffpack_ppluq.inl"#include "ffpack_ludivine.inl"#include "ffpack_ludivine_mp.inl"#include "ffpack_echelonforms.inl"#include "ffpack_invert.inl"#include "ffpack_ftrtr.inl"#include "ffpack_charpoly_kglu.inl"#include "ffpack_charpoly_kgfast.inl"#include "ffpack_charpoly_kgfastgeneralized.inl"#include "ffpack_charpoly_danilevski.inl"#include "ffpack_charpoly.inl"#include "ffpack_frobenius.inl"#include "ffpack_minpoly.inl"#include "ffpack_krylovelim.inl"#include "ffpack_permutation.inl"#include "ffpack_rankprofiles.inl"#include "ffpack_det_mp.inl"#include "ffpack.inl"Namespaces | |
| FFPACK | |
| Finite Field PACK Set of elimination based routines for dense linear algebra. | |
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. | |
| 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) |
| Computes P1 x Diag (I_R, P2) where P1 is a LAPACK and P2 a LAPACK permutation and store the result in P1 as a LAPACK permutation. 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 | 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  or  . 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, const size_t threshold=__FFLASFFPACK_FTRTRI_THRESHOLD) |
| Compute the inverse of a triangular matrix. More... | |
| template<class Field > | |
| void | ftrtrm (const Field &F, const FFLAS::FFLAS_SIDE side, 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 > | |
| bool | fsytrf (const Field &F, const FFLAS::FFLAS_UPLO UpLo, const size_t N, typename Field::Element_ptr A, const size_t lda, const size_t threshold=__FFLASFFPACK_FSYTRF_THRESHOLD) |
| Triangular factorization of symmetric matrices. More... | |
| template<class Field > | |
| bool | fsytrf_nonunit (const Field &F, const FFLAS::FFLAS_UPLO UpLo, const size_t N, typename Field::Element_ptr A, const size_t lda, typename Field::Element_ptr D, const size_t incD, const size_t threshold=__FFLASFFPACK_FSYTRF_THRESHOLD) |
| Triangular factorization of symmetric matrices. 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, size_t BCThreshold=__FFLASFFPACK_PLUQ_THRESHOLD) |
| Compute a 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=__FFLASFFPACK_LUDIVINE_THRESHOLD) |
| Compute the CUP or PLE factorization of the given matrix. More... | |
| 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 | GaussJordan (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 *P, size_t *Q, const FFPACK::FFPACK_LU_TAG LuTag) |
| Gauss-Jordan algorithm computing the Reduced Row echelon form and its transform matrix. 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 PolRing > | |
| std::list< typename PolRing::Element > & | CharPoly (const PolRing &R, std::list< typename PolRing::Element > &charp, const size_t N, typename PolRing::Domain_t::Element_ptr A, const size_t lda, typename PolRing::Domain_t::RandIter &G, const FFPACK_CHARPOLY_TAG CharpTag=FfpackAuto) |
| Compute the characteristic polynomial of the matrix A. More... | |
| template<class PolRing > | |
| PolRing::Element & | CharPoly (const PolRing &R, typename PolRing::Element &charp, const size_t N, typename PolRing::Domain_t::Element_ptr A, const size_t lda, typename PolRing::Domain_t::RandIter &G, const FFPACK_CHARPOLY_TAG CharpTag=FfpackAuto) |
| Compute the characteristic polynomial of the matrix A. More... | |
| template<class PolRing > | |
| PolRing::Element & | CharPoly (const PolRing &R, typename PolRing::Element &charp, const size_t N, typename PolRing::Domain_t::Element_ptr A, const size_t lda, const FFPACK_CHARPOLY_TAG CharpTag=FfpackAuto) |
| Compute the characteristic polynomial of the matrix A. More... | |
| template<class PolRing > | |
| std::list< typename PolRing::Element > & | CharpolyArithProg (const PolRing &R, std::list< typename PolRing::Element > &frobeniusForm, const size_t N, typename PolRing::Domain_t::Element_ptr A, const size_t lda, typename PolRing::Domain_t::RandIter &G, const size_t block_size=__FFLASFFPACK_ARITHPROG_THRESHOLD) |
| 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) |
| Compute the minimal polynomial of the matrix A. More... | |
| template<class Field , class Polynomial , class RandIter > | |
| Polynomial & | MinPoly (const Field &F, Polynomial &minP, const size_t N, typename Field::ConstElement_ptr A, const size_t lda, RandIter &G) |
| Compute the minimal polynomial of the matrix A. More... | |
| template<class Field , class Polynomial > | |
| Polynomial & | MatVecMinPoly (const Field &F, Polynomial &minP, const size_t N, typename Field::ConstElement_ptr A, const size_t lda, typename Field::ConstElement_ptr v, const size_t incv) |
Compute the minimal polynomial of the matrix A and a vector v, namely the first linear dependency relation in the Krylov basis  . 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 (typename Field::Element &det, 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 *Q, const FFLAS::FFLAS_DIAG Diag=FFLAS::FflasNonUnit) |
| Returns the determinant of the given matrix. 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) |
| Solves a linear system AX = b using LQUP factorization. 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) |
| Solve L X = B or X L = B in place. 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  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... | |
Detailed Description
Set of elimination based routines for dense linear algebra.
Matrices are supposed over finite prime field of characteristic less than 2^26.
Function Documentation
◆ GaussJordan()
|
inline |
Gauss-Jordan algorithm computing the Reduced Row echelon form and its transform matrix.
- Bibliography:
- Algorithm 2.8 of A. Storjohann Thesis 2000,
- Algorithm 11 of Jeannerod C-P., Pernet, C. and Storjohann, A.
Rank-profilerevealing Gaussian elimination and the CUP matrix decomposition , J. of Symbolic Comp., 2013
- Parameters
-
M row dimension of A N column dimension of A [in,out] A an m x n matrix lda leading dimension of A P row permutation Q column permutation LuTag set the base case to a Tile (FfpackGaussJordanTile) or Slab (FfpackGaussJordanSlab) recursive RedEchelon
| I | A11 | A12 | | |-—|--—|--—|-—| | |I | *| A22 | | | |0 | 0| A22 | | |-—|--—|--—|-—| | | 0 | A32 | | |-—|--—|--—|-—|
where the transformation matrix is stored at the pivot column position
◆ CharpolyArithProg()
| std::list< typename PolRing::Element > & CharpolyArithProg | ( | const PolRing & | R, |
| std::list< typename PolRing::Element > & | frobeniusForm, | ||
| const size_t | N, | ||
| typename PolRing::Domain_t::Element_ptr | A, | ||
| const size_t | lda, | ||
| typename PolRing::Domain_t::RandIter & | G, | ||
| const size_t | block_size = __FFLASFFPACK_ARITHPROG_THRESHOLD |
||
| ) |
