linbox
1
|
Set of elimination based routines for dense linear algebra with matrices over finite prime field of characteristic less than 2^26. More...
#include <ffpack.h>
Inherits FFLAS.
Static Public Member Functions | |
template<class Field > | |
static size_t | Rank (const Field &F, const size_t M, const size_t N, typename Field::Element *A, const size_t lda) |
using LQUP factorization. | |
template<class Field > | |
static bool | IsSingular (const Field &F, const size_t M, const size_t N, typename Field::Element *A, const size_t lda) |
using LQUP factorization with early termination. | |
template<class Field > | |
static Field::Element | Det (const Field &F, const size_t M, const size_t N, typename Field::Element *A, const size_t lda) |
using LQUP factorization with early termination. | |
template<class Field > | |
static void | fgetrs (const Field &F, const FFLAS_SIDE Side, const size_t M, const size_t N, const size_t R, typename Field::Element *A, const size_t lda, const size_t *P, const size_t *Q, typename Field::Element *B, const size_t ldb, int *info) |
template<class Field > | |
static Field::Element * | fgetrs (const Field &F, const FFLAS_SIDE Side, const size_t M, const size_t N, const size_t NRHS, const size_t R, typename Field::Element *A, const size_t lda, const size_t *P, const size_t *Q, typename Field::Element *X, const size_t ldx, const typename Field::Element *B, const size_t ldb, int *info) |
template<class Field > | |
static size_t | fgesv (const Field &F, const FFLAS_SIDE Side, const size_t M, const size_t N, typename Field::Element *A, const size_t lda, typename Field::Element *B, const size_t ldb, int *info) |
Square system solver. | |
template<class Field > | |
static size_t | fgesv (const Field &F, const FFLAS_SIDE Side, const size_t M, const size_t N, const size_t NRHS, typename Field::Element *A, const size_t lda, typename Field::Element *X, const size_t ldx, const typename Field::Element *B, const size_t ldb, int *info) |
Rectangular system solver. | |
template<class Field > | |
static Field::Element * | Solve (const Field &F, const size_t M, typename Field::Element *A, const size_t lda, typename Field::Element *x, const int incx, const typename Field::Element *b, const int incb) |
Solve linear system using LQUP factorization. | |
template<class Field > | |
static Field::Element * | Invert (const Field &F, const size_t M, typename Field::Element *A, const size_t lda, int &nullity) |
Invert a matrix or return its nullity. | |
template<class Field > | |
static Field::Element * | Invert2 (const Field &F, const size_t M, typename Field::Element *A, const size_t lda, typename Field::Element *X, const size_t ldx, int &nullity) |
Invert a matrix or return its nullity. | |
template<class Field > | |
static size_t | RowRankProfile (const Field &F, const size_t M, const size_t N, typename Field::Element *A, const size_t lda, size_t *rkprofile) |
template<class Field > | |
static size_t | ColumnRankProfile (const Field &F, const size_t M, const size_t N, typename Field::Element *A, const size_t lda, size_t *rkprofile) |
template<class Field > | |
static size_t | RowRankProfileSubmatrixIndices (const Field &F, const size_t M, const size_t N, typename Field::Element *A, const size_t lda, size_t *&rowindices, size_t *&colindices, size_t &R) |
template<class Field > | |
static size_t | ColRankProfileSubmatrixIndices (const Field &F, const size_t M, const size_t N, typename Field::Element *A, const size_t lda, size_t *&rowindices, size_t *&colindices, size_t &R) |
template<class Field > | |
static size_t | RowRankProfileSubmatrix (const Field &F, const size_t M, const size_t N, typename Field::Element *A, const size_t lda, typename Field::Element *&X, size_t &R) |
template<class Field > | |
static size_t | ColRankProfileSubmatrix (const Field &F, const size_t M, const size_t N, typename Field::Element *A, const size_t lda, typename Field::Element *&X, size_t &R) |
template<class Field > | |
static Field::Element * | LQUPtoInverseOfFullRankMinor (const Field &F, const size_t rank, typename Field::Element *A_factors, const size_t lda, const size_t *QtPointer, typename Field::Element *X, const size_t ldx) |
template<class Field > | |
static size_t | LUdivine (const Field &F, const FFLAS_DIAG Diag, const FFLAS_TRANSPOSE trans, const size_t M, const size_t N, typename Field::Element *A, const size_t lda, size_t *P, size_t *Qt, const FFPACK_LUDIVINE_TAG LuTag=FfpackLQUP, const size_t cutoff=__FFPACK_LUDIVINE_CUTOFF) |
LQUP factorization. | |
template<class Field > | |
static void | ftrtri (const Field &F, const FFLAS_UPLO Uplo, const FFLAS_DIAG Diag, const size_t N, typename Field::Element *A, const size_t lda) |
template<class Field > | |
static void | ftrtrm (const Field &F, const FFLAS_DIAG diag, const size_t N, typename Field::Element *A, const size_t lda) |
template<class Field > | |
static size_t | ColumnEchelonForm (const Field &F, const size_t M, const size_t N, typename Field::Element *A, const size_t lda, size_t *P, size_t *Qt) |
template<class Field > | |
static size_t | RowEchelonForm (const Field &F, const size_t M, const size_t N, typename Field::Element *A, const size_t lda, size_t *P, size_t *Qt) |
template<class Field > | |
static size_t | ReducedColumnEchelonForm (const Field &F, const size_t M, const size_t N, typename Field::Element *A, const size_t lda, size_t *P, size_t *Qt) |
template<class Field > | |
static size_t | ReducedRowEchelonForm (const Field &F, const size_t M, const size_t N, typename Field::Element *A, const size_t lda, size_t *P, size_t *Qt) |
template<class Field > | |
static void | applyP (const Field &F, const FFLAS_SIDE Side, const FFLAS_TRANSPOSE Trans, const size_t M, const int ibeg, const int iend, typename Field::Element *A, const size_t lda, const size_t *P) |
template<class Field , class Polynomial > | |
static std::list< Polynomial > & | CharPoly (const Field &F, std::list< Polynomial > &charp, const size_t N, typename Field::Element *A, const size_t lda, const FFPACK_CHARPOLY_TAG CharpTag=FfpackLUK) |
template<class Field , class Polynomial > | |
static Polynomial & | MinPoly (const Field &F, Polynomial &minP, const size_t N, const typename Field::Element *A, const size_t lda, typename Field::Element *X, const size_t ldx, size_t *P, const FFPACK_MINPOLY_TAG MinTag, const size_t kg_mc, const size_t kg_mb, const size_t kg_j) |
![]() | |
template<class Field > | |
static void | fgemv (const Field &F, const FFLAS_TRANSPOSE TransA, const size_t M, const size_t N, const typename Field::Element alpha, const typename Field::Element *A, const size_t lda, const typename Field::Element *X, const size_t incX, const typename Field::Element beta, typename Field::Element *Y, const size_t incY) |
finite prime Field GEneral Matrix Vector multiplication | |
template<class Field > | |
static void | fger (const Field &F, const size_t M, const size_t N, const typename Field::Element alpha, const typename Field::Element *x, const size_t incx, const typename Field::Element *y, const size_t incy, typename Field::Element *A, const size_t lda) |
fger: GEneral ? | |
template<class Field > | |
static void | ftrsv (const Field &F, const FFLAS_UPLO Uplo, const FFLAS_TRANSPOSE TransA, const FFLAS_DIAG Diag, const size_t N, const typename Field::Element *A, const size_t lda, typename Field::Element *X, int incX) |
ftrsv: TRiangular System solve with Vector Computes X <- op(A^-1).X\ size of X is N | |
template<class Field > | |
static Field::Element * | fgemm (const Field &F, const FFLAS_TRANSPOSE ta, const FFLAS_TRANSPOSE tb, const size_t m, const size_t n, const size_t k, const typename Field::Element alpha, const typename Field::Element *A, const size_t lda, const typename Field::Element *B, const size_t ldb, const typename Field::Element beta, typename Field::Element *C, const size_t ldc, const size_t w) |
Field GEneral Matrix Multiply. | |
template<class Field > | |
static Field::Element * | fgemm (const Field &F, const FFLAS_TRANSPOSE ta, const FFLAS_TRANSPOSE tb, const size_t m, const size_t n, const size_t k, const typename Field::Element alpha, const typename Field::Element *A, const size_t lda, const typename Field::Element *B, const size_t ldb, const typename Field::Element beta, typename Field::Element *C, const size_t ldc) |
Field GEneral Matrix Multiply. | |
template<class Field > | |
static Field::Element * | MatCopy (const Field &F, const size_t M, const size_t N, const typename Field::Element *A, const size_t lda) |
Additional Inherited Members | |
![]() | |
template<class Field > | |
static void | MatMulParameters (const Field &F, const size_t k, const typename Field::Element &beta, size_t &delayedDim, FFLAS_BASE &base, size_t &winoRecLevel, bool winoLevelProvided=false) |
Computes the threshold parameters for the cascade Matmul algorithm. | |
template<class Field > | |
static size_t | DotProdBound (const Field &F, const size_t w, const typename Field::Element &beta, const FFLAS_BASE base) |
computes the maximal size for delaying the modular reduction in a dotproduct | |
template<class Field > | |
static double | computeFactor (const Field &F, const size_t w) |
static size_t | WinoSteps (const size_t m) |
Computes the number of recursive levels to perform. | |
template<class Field > | |
static FFLAS_BASE | BaseCompute (const Field &F, const size_t w) |
Determines the type of floating point representation to convert to, for BLAS computations. | |
template<class Field > | |
static size_t | TRSMBound (const Field &F) |
computes the maximal size for delaying the modular reduction in a triangular system resolution |
Set of elimination based routines for dense linear algebra with matrices over finite prime field of characteristic less than 2^26.
This class only provides a set of static member functions. No instantiation is allowed.
It enlarges the set of BLAS routines of the class FFLAS, with higher level routines based on elimination.
|
inlinestatic |
using LQUP factorization.
Computes the rank of the given matrix using a LQUP factorization. The input matrix is modified.
M | row dimension of the matrix |
N | column dimension of the matrix |
A | input matrix |
lda | leading dimension of A |
|
inlinestatic |
using LQUP factorization with early termination.
Returns true if the given matrix is singular. The method is a block elimination with early termination The input matrix is modified.
M | row dimension of the matrix |
N | column dimension of the matrix |
A | input matrix |
lda | leading dimension of A |
|
inlinestatic |
using LQUP factorization with early termination.
Returns the determinant of the given matrix. The method is a block elimination with early termination The input matrix is modified.
M | row dimension of the matrix |
N | column dimension of the matrix |
A | input matrix |
lda | leading dimension of A |
|
inlinestatic |
Solve the system A X = B or X A = B, using the LQUP decomposition of A already computed inplace with LUdivine(FflasNoTrans, FflasNonUnit). Version for A square. If A is rank deficient, a solution is returned if the system is consistent, Otherwise an info is 1
Side | Determine wheter the resolution is left or right looking. |
M | row dimension of B |
N | col dimension of B |
R | rank of A |
A | input matrix |
lda | leading dimension of A |
P | column permutation of the LQUP decomposition of A |
Q | column permutation of the LQUP decomposition of A |
B | Right/Left hand side matrix. Initially stores B, finally stores the solution X. |
ldb | leading dimension of B Succes of the computation: 0 if successfull, >0 if system is inconsistent |
|
inlinestatic |
Solve the system A X = B or X A = B, using the LQUP decomposition of A already computed inplace with LUdivine(FflasNoTrans, FflasNonUnit). Version for A rectangular. If A is rank deficient, a solution is returned if the system is consistent, Otherwise an info is 1
Side | Determine wheter the resolution is left or right looking. |
M | row dimension of A |
N | col dimension of A |
NRHS | number of columns (if Side = FflasLeft) or row (if Side = FflasRight) of the matrices X and B |
R | rank of A |
A | input matrix |
lda | leading dimension of A |
P | column permutation of the LQUP decomposition of A |
Q | column permutation of the LQUP decomposition of A |
X | solution matrix |
ldx | leading dimension of X |
B | Right/Left hand side matrix. |
ldb | leading dimension of B |
info | Succes of the computation: 0 if successfull, >0 if system is inconsistent |
|
inlinestatic |
Square system solver.
Field | The computation domain |
Side | Determine wheter the resolution is left or right looking |
M | row dimension of B |
N | col dimension of B |
A | input matrix |
lda | leading dimension of A |
P | column permutation of the LQUP decomposition of A |
Q | column permutation of the LQUP decomposition of A |
B | Right/Left hand side matrix. Initially contains B, finally contains the solution X. |
ldb | leading dimension of B |
info | Success of the computation: 0 if successfull, >0 if system is inconsistent |
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
|
inlinestatic |
Rectangular system solver.
Field | The computation domain |
Side | Determine wheter the resolution is left or right looking |
M | row dimension of A |
N | col dimension of A |
NRHS | number of columns (if Side = FflasLeft) or row (if Side = FflasRight) of the matrices X and B |
A | input matrix |
lda | leading dimension of A |
P | column permutation of the LQUP decomposition of A |
Q | column permutation of the LQUP decomposition of A |
B | Right/Left hand side matrix. Initially contains B, finally contains the solution X. |
ldb | leading dimension of B Success of the computation: 0 if successfull, >0 if system is inconsistent |
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
|
inlinestatic |
Solve linear system using LQUP factorization.
Solve the system Ax=b, using LQUP factorization and two triangular system resolutions. The input matrix is modified.
M | row dimension of the matrix |
A | input matrix |
lda | leading dimension of A |
x | solution vector |
incX | increment of x |
b | right hand side vector |
incB | increment of b |
|
inlinestatic |
Invert a matrix or return its nullity.
Invert the given matrix in place or computes its nullity if it is singular. An inplace 2n^3 algorithm is used.
M | order of the matrix |
A | input matrix |
lda | leading dimension of A |
nullity | dimension of the kernel of A |
|
inlinestatic |
Invert a matrix or return its nullity.
Invert the given matrix or computes its nullity if it is singular. An 2n^3 algorithm is used. The input matrix is modified.
M | order of the matrix |
A | input matrix |
lda | leading dimension of A |
X | inverse of A |
ldx | leading dimension of X |
nullity | dimension of the kernel of A |
|
inlinestatic |
RowRankProfile Computes the row rank profile of A.
A,: | input matrix of dimension |
rklprofile,: | return the rank profile as an array of row indexes, of dimension r=rank(A) |
rkprofile is allocated during the computation. Returns R
|
inlinestatic |
ColumnRankProfile Computes the column rank profile of A.
A,: | input matrix of dimension |
rklprofile,: | return the rank profile as an array of row indexes, of dimension r=rank(A) |
A is modified rkprofile is allocated during the computation. Returns R
|
inlinestatic |
RowRankProfileSubmatrixIndices Computes the indices of the submatrix r*r X of A whose rows correspond to the row rank profile of A.
A,: | input matrix of dimension |
rowindices,: | array of the row indices of X in A |
colindices,: | array of the col indices of X in A |
rowindices and colindices are allocated during the computation. A is modified Returns R
|
inlinestatic |
ColRankProfileSubmatrixIndices Computes the indices of the submatrix r*r X of A whose columns correspond to the column rank profile of A.
A,: | input matrix of dimension |
rowindices,: | array of the row indices of X in A |
colindices,: | array of the col indices of X in A |
rowindices and colindices are allocated during the computation. A is modified Returns R
|
inlinestatic |
RowRankProfileSubmatrix Compute the r*r submatrix X of A, by picking the row rank profile rows of A
A,: | input matrix of dimension M x N |
X,: | the output matrix |
A is not modified X is allocated during the computation. Returns R
|
inlinestatic |
ColRankProfileSubmatrix Compute the r*r submatrix X of A, by picking the row rank profile rows of A
A,: | input matrix of dimension M x N |
X,: | the output matrix |
A is not modified X is allocated during the computation. Returns R
|
inlinestatic |
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)
rank,: | rank of the matrix. |
A_factors,: | matrix containing the L and U entries of the factorization |
QtPointer,: | theLQUP->getQ()->getPointer() (note: getQ returns Qt!) |
X,: | desired location for output |
|
static |
LQUP factorization.
Compute the LQUP factorization of the given matrix using a block agorithm and return its rank. The permutations P and Q are represented using LAPACK's convention.
Diag | precise whether U should have a unit diagonal or not |
M | matrix row dimension |
N | matrix column dimension |
A | input matrix |
lda | leading dimension of A |
P | the column permutation |
Qt | the transpose of the row permutation Q |
LuTag | flag for setting the earling termination if the matrix is singular |
|
inlinestatic |
Compute the inverse of a triangular matrix.
Uplo | whether the matrix is upper of lower triangular |
Diag | whether the matrix if unit diagonal |
|
inlinestatic |
Compute the 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
|
inlinestatic |
Compute the Column Echelon form of the input matrix in-place.
After the computation A = [ M \ V ] such that AU = C is a column echelon decomposition of A, with U = P^T [ V + Ir ] and C = M //+ Q [ Ir ] [ 0 In-r ] // [ 0 ] Qt = Q^T
|
inlinestatic |
Compute the Row Echelon form of the input matrix in-place.
After the computation A = [ L \ M ] such that L A = R is a column echelon decomposition of A, with L = [ L+Ir 0 ] P and R = M [ In-r ] Qt = Q^T
|
inlinestatic |
Compute the Reduced Column Echelon form of the input matrix in-place.
After the computation A = [ V ] such that AU = R is a reduced column echelon [ M 0 ] decomposition of A, where U = P^T [ V ] and R = Q [ Ir ] [ 0 In-r ] [ M 0 ] Qt = Q^T
|
inlinestatic |
Compute the Reduced Row Echelon form of the input matrix in-place.
After the computation A = [ V ] such that L A = R is a reduced row echelon [ M 0 ] decomposition of A, where L = [ V ] P^T and R = [ Ir M ] Q [ 0 In-r ] [ 0 ] Qt = Q^T
|
inlinestatic |
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) Side==FflasLeft for row permutation Side==FflasRight for a column permutation Trans==FflasTrans for the inverse permutation of P
|
static |
Compute the characteristic polynomial of A using Krylov Method, and LUP factorization of the Krylov matrix
|
static |
Compute the minimal polynomial 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