FflasFfpack
Data Structures | Namespaces | Macros | Enumerations | Functions
ffpack.h File Reference

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 "ffpack_fgesv.inl"
#include "ffpack_fgetrs.inl"
#include "ffpack_ftrtr.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"

Data Structures

class  CharpolyFailed
 
class  callLUdivine_small< Element >
 

Namespaces

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

Macros

#define __FFPACK_LUDIVINE_CUTOFF   0
 
#define __FFPACK_CHARPOLY_THRESHOLD   30
 

Enumerations

Functions

void LAPACKPerm2MathPerm (size_t *MathP, const size_t *LapackP, const size_t N)
 Conversion of a permutation from LAPACK format to Math format. More...
 
void MathPerm2LAPACKPerm (size_t *LapackP, const size_t *MathP, const size_t N)
 Conversion of a permutation from Maths format to LAPACK format. More...
 
template<class Field >
void MatrixApplyS (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)
 
template<class Element >
void PermApplyS (Element *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)
 
template<class Field >
void MatrixApplyT (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)
 
template<class Element >
void PermApplyT (Element *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)
 
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 ]. More...
 
void composePermutationsQ (size_t *MathP, const size_t *Q1, const size_t *Q2, const size_t R, const size_t N)
 
void cyclic_shift_mathPerm (size_t *P, const size_t s)
 
template<typename Base_t >
void cyclic_shift_row_col (Base_t *A, size_t m, size_t n, size_t lda)
 
template<class Field >
void cyclic_shift_row (const Field &F, typename Field::Element_ptr A, size_t m, size_t n, size_t lda)
 
template<class Field >
void cyclic_shift_col (const Field &F, typename Field::Element_ptr A, size_t m, size_t n, size_t lda)
 
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 submatrix of P (between ibeg and iend) to a matrix to (iend-ibeg) vectors of size M stored in A (as column for NoTrans and rows for Trans). 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. More...
 
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. More...
 
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. More...
 
template<class Field >
size_t pPLUQ (const Field &Fi, 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, int nt)
 
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 trinv_left (const Field &F, const size_t N, typename Field::ConstElement_ptr L, const size_t ldl, typename Field::Element_ptr X, const size_t ldx)
 
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=__FFPACK_LUDIVINE_CUTOFF)
 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. More...
 
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. More...
 
template<class Field >
size_t LUdivine_construct (const Field &F, const FFLAS::FFLAS_DIAG Diag, const size_t M, const size_t N, typename Field::ConstElement_ptr A, const size_t lda, typename Field::Element_ptr X, const size_t ldx, typename Field::Element_ptr u, size_t *P, bool computeX, const FFPACK_MINPOLY_TAG MinTag=FfpackDense, const size_t kg_mc=0, const size_t kg_mb=0, const size_t kg_j=0)
 
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. More...
 
template<class Polynomial , class Field >
Polynomialmulpoly (const Field &F, Polynomial &res, const Polynomial &P1, const Polynomial &P2)
 
template<class Field , class Polynomial >
PolynomialCharPoly (const Field &F, Polynomial &charp, const size_t N, typename Field::Element_ptr A, const size_t lda, const FFPACK_CHARPOLY_TAG CharpTag=FfpackArithProg)
 
template<class Field , class Polynomial >
std::list< Polynomial > & KellerGehrig (const Field &F, std::list< Polynomial > &charp, const size_t N, typename Field::ConstElement_ptr A, const size_t lda)
 
template<class Field , class Polynomial >
int KGFast (const Field &F, std::list< Polynomial > &charp, const size_t N, typename Field::Element_ptr A, const size_t lda, size_t *kg_mc, size_t *kg_mb, size_t *kg_j)
 
template<class Field , class Polynomial >
std::list< Polynomial > & KGFast_generalized (const Field &F, std::list< Polynomial > &charp, const size_t N, typename Field::Element_ptr A, const size_t lda)
 
template<class Field >
void fgemv_kgf (const Field &F, const size_t N, typename Field::ConstElement_ptr A, const size_t lda, typename Field::ConstElement_ptr X, const size_t incX, typename Field::Element_ptr Y, const size_t incY, const size_t kg_mc, const size_t kg_mb, const size_t kg_j)
 
template<class Field , class Polynomial >
std::list< Polynomial > & LUKrylov (const Field &F, std::list< Polynomial > &charp, const size_t N, typename Field::Element_ptr A, const size_t lda, typename Field::Element_ptr U, const size_t ldu)
 
template<class Field , class Polynomial >
std::list< Polynomial > & Danilevski (const Field &F, std::list< Polynomial > &charp, const size_t N, typename Field::Element_ptr A, const size_t lda)
 
template<class Field , class Polynomial >
std::list< Polynomial > & LUKrylov_KGFast (const Field &F, std::list< Polynomial > &charp, const size_t N, typename Field::Element_ptr A, const size_t lda, typename Field::Element_ptr X, const size_t ldx)
 
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 >
PolynomialMinPoly (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 KrylovElim (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 size_t deg, size_t *iterates, size_t *inviterates, const size_t maxit, size_t virt)
 
template<class Field >
size_t SpecRankProfile (const Field &F, const size_t M, const size_t N, typename Field::Element_ptr A, const size_t lda, const size_t deg, size_t *rankProfile)
 
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. More...
 
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. More...
 
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.

Macro Definition Documentation

#define __FFPACK_LUDIVINE_CUTOFF   0
#define __FFPACK_CHARPOLY_THRESHOLD   30