FFLAS-FFPACK
|
Set of elimination based routines for dense linear algebra. More...
#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_ftrtr.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_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.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. | |
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 ![]() ![]() | |
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 ![]() | |
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\U 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\U 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\U 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\U 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\U 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\U 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\U 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\U 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... | |
Set of elimination based routines for dense linear algebra.
Matrices are supposed over finite prime field of characteristic less than 2^26.