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 "fflas-ffpack/fflas/fflas_helpers.inl"
#include <list>
#include <vector>
#include <iostream>
#include <algorithm>
#include "fflas-ffpack/checkers/checkers_ffpack.h"
#include "ffpack_fgesv.inl"
#include "ffpack_fgetrs.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_fsytrf.inl"
#include "ffpack_invert.inl"
#include "ffpack_ftrtr.inl"
#include "ffpack_ftrstr.inl"
#include "ffpack_ftrssyr2k.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_bruhatgen.inl"
#include "ffpack_sss.inl"
#include "ffpack.inl"

Namespaces
namespace	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.

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.

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\).

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.

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.

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.

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.

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 of two triangular matrices of opposite shape.

template<class Field>
void	ftrstr (const Field &F, const FFLAS::FFLAS_SIDE side, const FFLAS::FFLAS_UPLO Uplo, const FFLAS::FFLAS_DIAG diagA, const FFLAS::FFLAS_DIAG diagB, const size_t N, typename Field::ConstElement_ptr A, const size_t lda, typename Field::Element_ptr B, const size_t ldb, const size_t threshold=64)
	Solve a triangular system with a triangular right hand side of the same shape.

template<class Field>
void	ftrssyr2k (const Field &F, const FFLAS::FFLAS_UPLO Uplo, const FFLAS::FFLAS_DIAG diagA, const size_t N, typename Field::ConstElement_ptr A, const size_t lda, typename Field::Element_ptr B, const size_t ldb, const size_t threshold=64)
	Solve a triangular system in a symmetric sum: find B upper/lower triangular such that A^T B + B^T A = C where C is symmetric.

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.

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.

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 a PLUQ factorization of the given matrix; such that A=PLUQ.

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.

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.

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.

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.

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.

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.

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.

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 or computes its nullity if it is singular.

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.

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, const size_t degree=__FFLASFFPACK_ARITHPROG_THRESHOLD)
	Compute the characteristic polynomial of the matrix A.

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, const size_t degree=__FFLASFFPACK_ARITHPROG_THRESHOLD)
	Compute the characteristic polynomial of the matrix A.

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, const size_t degree=__FFLASFFPACK_ARITHPROG_THRESHOLD)
	Compute the characteristic polynomial of the matrix A.

template<class PolRing>
void	RandomKrylovPrecond (const PolRing &PR, std::list< typename PolRing::Element > &completedFactors, const size_t N, typename PolRing::Domain_t::Element_ptr A, const size_t lda, size_t &Nb, typename PolRing::Domain_t::Element_ptr &B, size_t &ldb, typename PolRing::Domain_t::RandIter &g, const size_t degree=__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.

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.

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 \((v,Av, ..., A^Nv)\).

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 PLUQ factorization.

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.

template<class Field>
Field::Element &	Det (const Field &F, typename Field::Element &det, const size_t N, typename Field::Element_ptr A, const size_t lda, size_t P=NULL, size_t Q=NULL)
	Returns the determinant of the given square matrix.

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 PLUQ factorization.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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>
size_t	LTBruhatGen (const Field &Fi, const FFLAS::FFLAS_DIAG diag, const size_t N, typename Field::Element_ptr A, const size_t lda, size_t P, size_t Q)
	LTBruhatGen Suppose A is Left Triangular Matrix This procedure computes the Bruhat Representation of A and return the rank of A.

template<class Field>
void	getLTBruhatGen (const Field &Fi, const size_t N, const size_t r, const size_t P, const size_t Q, typename Field::Element_ptr R, const size_t ldr)
	GetLTBruhatGen This procedure Computes the Rank Revealing Matrix based on the Bruhta representation of a Matrix.

template<class Field>
void	getLTBruhatGen (const Field &Fi, const FFLAS::FFLAS_UPLO Uplo, const FFLAS::FFLAS_DIAG diag, 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)
	GetLTBruhatGen This procedure computes the matrix L or U f the Bruhat Representation Suppose that A is the bruhat representation of a matrix.

size_t	LTQSorder (const size_t N, const size_t r, const size_t P, const size_t Q)
	LTQSorder This procedure computes the order of quasiseparability of a matrix.

template<class Field>
size_t	CompressToBlockBiDiagonal (const Field &Fi, const FFLAS::FFLAS_UPLO Uplo, size_t N, size_t s, size_t r, const size_t P, const size_t Q, typename Field::Element_ptr A, size_t lda, typename Field::Element_ptr X, size_t ldx, size_t K, size_t M, size_t *T)
	CompressToBlockBiDiagonal This procedure compress a compact representation of a row echelon form or column echelon form.

template<class Field>
void	ExpandBlockBiDiagonalToBruhat (const Field &Fi, const FFLAS::FFLAS_UPLO Uplo, size_t N, size_t s, size_t r, typename Field::Element_ptr A, size_t lda, typename Field::Element_ptr X, size_t ldx, size_t NbBlocks, size_t K, size_t M, size_t *T)
	ExpandBlockBiDiagonal This procedure expand a compact representation of a row echelon form or column echelon form.

void	Bruhat2EchelonPermutation (size_t N, size_t R, const size_t P, const size_t Q, size_t *M)
	Bruhat2EchelonPermutation (N,R,P,Q) Compute M such that LM or MU is in echelon form where L or U are factors of the Bruhat Rpresentation.

template<class Field>
void	productBruhatxTS (const Field &Fi, size_t N, size_t s, size_t r, const size_t P, const size_t Q, const typename Field::Element_ptr Xu, size_t ldu, size_t NbBlocksU, size_t Ku, size_t Tu, size_t MU, const typename Field::Element_ptr Xl, size_t ldl, size_t NbBlocksL, size_t Kl, size_t Tl, size_t ML, typename Field::Element_ptr B, size_t t, size_t ldb, typename Field::Element_ptr C, size_t ldc)
	productBruhatxTS Comput the product between the CRE compact representation of a matrix A and B a tall matrix

template<class Field>
void	productSSSxTS (const Field &Fi, size_t N, size_t s, typename Field::ConstElement_ptr P, size_t ldp, typename Field::ConstElement_ptr Q, size_t ldq, typename Field::ConstElement_ptr R, size_t ldr, typename Field::ConstElement_ptr U, size_t ldu, typename Field::ConstElement_ptr V, size_t ldv, typename Field::ConstElement_ptr W, size_t ldw, typename Field::ConstElement_ptr D, size_t ldd, size_t t, const typename Field::Element alpha, typename Field::Element_ptr B, size_t ldb, const typename Field::Element beta, typename Field::Element_ptr C, size_t ldc)
	Compute the product of a quasi-separable matrix A, represented by a sequentially semi-separable generator, with a dense rectangular matrix B: \( C \gets \alpha * A \times B + beta C \).

template<class Field>
void	SSSToDense (const Field &Fi, size_t N, size_t s, typename Field::ConstElement_ptr P, size_t ldp, typename Field::ConstElement_ptr Q, size_t ldq, typename Field::ConstElement_ptr R, size_t ldr, typename Field::ConstElement_ptr U, size_t ldu, typename Field::ConstElement_ptr V, size_t ldv, typename Field::ConstElement_ptr W, size_t ldw, typename Field::ConstElement_ptr D, size_t ldd, typename Field::Element_ptr A, size_t lda)
	Computes a quasi-separable matrix A from its SSS generators.

template<class Field>
void	DenseToSSS (const Field &Fi, size_t N, size_t s, typename Field::Element_ptr P, size_t ldp, typename Field::Element_ptr Q, size_t ldq, typename Field::Element_ptr R, size_t ldr, typename Field::Element_ptr U, size_t ldu, typename Field::Element_ptr V, size_t ldv, typename Field::Element_ptr W, size_t ldw, typename Field::Element_ptr D, size_t ldd, typename Field::ConstElement_ptr A, size_t lda)
	Computes SSS generators for a quasi-separable matrix A.

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.

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()

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 )

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-profile revealing 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

◆ RandomKrylovPrecond()

template<class PolRing>

void RandomKrylovPrecond	(	const PolRing &	PR,
		std::list< typename PolRing::Element > &	completedFactors,
		const size_t	N,
		typename PolRing::Domain_t::Element_ptr	A,
		const size_t	lda,
		size_t &	Nb,
		typename PolRing::Domain_t::Element_ptr &	B,
		size_t &	ldb,
		typename PolRing::Domain_t::RandIter &	g,
		const size_t	degree = __FFLASFFPACK_ARITHPROG_THRESHOLD )

inline

Todo: swap to save space ??

Todo

Todo: don't assing K2 c*noc x N but only mas (c,noc) x N and store each one after the other

Namespaces

Functions

Detailed Description

Function Documentation

◆ GaussJordan()

◆ RandomKrylovPrecond()