FflasFfpack
Namespaces | Enumerations | Functions
fflas.h File Reference

Finite Field Linear Algebra Subroutines More...

#include <cmath>
#include <cstring>
#include "fflas-ffpack/config-blas.h"
#include "fflas-ffpack/field/unparametric.h"
#include "fflas-ffpack/field/modular-balanced.h"
#include "fflas-ffpack/field/modular-positive.h"
#include <float.h>
#include "fflas_bounds.inl"
#include "fflas_fgemm.inl"
#include "fflas_fgemv.inl"
#include "fflas_fger.inl"
#include "fflas_ftrsm.inl"
#include "fflas_ftrmm.inl"
#include "fflas_ftrsv.inl"
#include "fflas_faxpy.inl"
#include "fflas_fdot.inl"
#include "fflas_fcopy.inl"
#include "fflas_faddm.inl"

Namespaces

 FFLAS
 FFLAS: Finite Field Linear Algebra Subroutines.
 

Enumerations

Functions

template<class Field >
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. More...
 
template<class Field >
size_t DotProdBound (const Field &F, const size_t winoRecLevel, const typename Field::Element &beta, const FFLAS_BASE base)
 Computes the maximal size for delaying the modular reduction in a dotproduct. More...
 
template<class Field >
double computeFactorWino (const Field &F, const size_t w)
 Internal function for the bound computation. More...
 
template<class Field >
FFLAS_BASE BaseCompute (const Field &F, const size_t w)
 Determines the type of floating point representation to convert to, for BLAS computations. More...
 
template<class Field >
size_t TRSMBound (const Field &F)
 Computes the maximal size for delaying the modular reduction in a triangular system resolution. More...
 
template<class Field >
void fzero (const Field &F, const size_t n, typename Field::Element *X, const size_t incX)
 fzero : $A \gets 0 $. More...
 
template<class Field >
void fscal (const Field &F, const size_t n, const typename Field::Element alpha, typename Field::Element *X, const size_t incX)
 fscal $x \gets a \cdot x$. More...
 
template<class Field >
void fcopy (const Field &F, const size_t N, typename Field::Element *X, const size_t incX, const typename Field::Element *Y, const size_t incY)
 fcopy : $x \gets y $. More...
 
template<class Field >
void faxpy (const Field &F, const size_t N, const typename Field::Element alpha, const typename Field::Element *X, const size_t incX, typename Field::Element *Y, const size_t incY)
 faxpy : $y \gets \alpha \cdot x + y$. More...
 
template<class Field >
Field::Element fdot (const Field &F, const size_t N, const typename Field::Element *X, const size_t incX, const typename Field::Element *Y, const size_t incY)
 fdot: dot product $x^T y$. More...
 
template<class Field >
void fswap (const Field &F, const size_t N, typename Field::Element *X, const size_t incX, typename Field::Element *Y, const size_t incY)
 fswap: $ X \leftrightarrow Y$. More...
 
template<class Field >
void fcopy (const Field &F, const size_t m, const size_t n, typename Field::Element *A, const size_t lda, const typename Field::Element *B, const size_t ldb)
 fcopy : $A \gets B $. More...
 
template<class Field >
void fzero (const Field &F, const size_t m, const size_t n, typename Field::Element *A, const size_t lda)
 fzero : $A \gets 0 $. More...
 
template<class Field >
void fscal (const Field &F, const size_t m, const size_t n, const typename Field::Element alpha, typename Field::Element *A, const size_t lda)
 fscal $A \gets a \cdot A$. More...
 
template<class Field >
void fmove (const Field &F, const size_t m, const size_t n, typename Field::Element *A, const size_t lda, typename Field::Element *B, const size_t ldb)
 fmove : $A \gets B $ and $ B \gets 0$. More...
 
template<class Field >
void fadd (const Field &F, const size_t M, const size_t N, const typename Field::Element *A, const size_t lda, const typename Field::Element *B, const size_t ldb, typename Field::Element *C, const size_t ldc)
 fadd : matrix addition. More...
 
template<class Field >
void fsub (const Field &F, const size_t M, const size_t N, const typename Field::Element *A, const size_t lda, const typename Field::Element *B, const size_t ldb, typename Field::Element *C, const size_t ldc)
 fsub : matrix subtraction. More...
 
template<class Field >
void fsubin (const Field &F, const size_t M, const size_t N, const typename Field::Element *B, const size_t ldb, typename Field::Element *C, const size_t ldc)
 fsubin
 
template<class Field >
void faddin (const Field &F, const size_t M, const size_t N, const typename Field::Element *B, const size_t ldb, typename Field::Element *C, const size_t ldc)
 faddin
 
template<class Field >
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. More...
 
template<class Field >
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 ? More...
 
template<class Field >
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 \gets \mathrm{op}(A^{-1}) X$ More...
 
template<class Field >
void ftrsm (const Field &F, const FFLAS_SIDE Side, const FFLAS_UPLO Uplo, const FFLAS_TRANSPOSE TransA, const FFLAS_DIAG Diag, const size_t M, const size_t N, const typename Field::Element alpha, typename Field::Element *A, const size_t lda, typename Field::Element *B, const size_t ldb)
 ftrsm: TRiangular System solve with Matrix. More...
 
template<class Field >
void ftrmm (const Field &F, const FFLAS_SIDE Side, const FFLAS_UPLO Uplo, const FFLAS_TRANSPOSE TransA, const FFLAS_DIAG Diag, const size_t M, const size_t N, const typename Field::Element alpha, typename Field::Element *A, const size_t lda, typename Field::Element *B, const size_t ldb)
 ftrmm: TRiangular Matrix Multiply. More...
 
template<class Field >
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)
 fgemm: Field GEneral Matrix Multiply. More...
 
template<class Field >
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)
 fgemm: Field GEneral Matrix Multiply. More...
 
template<class Field >
Field::Element * fsquare (const Field &F, const FFLAS_TRANSPOSE ta, const size_t n, const typename Field::Element alpha, const typename Field::Element *A, const size_t lda, const typename Field::Element beta, typename Field::Element *C, const size_t ldc)
 fsquare: Squares a matrix. More...
 
template<class Field >
void faddm (const Field &F, const FFLAS_TRANSPOSE transA, const size_t M, const size_t N, const typename Field::Element *A, const size_t lda, typename Field::Element *B, const size_t ldb)
 faddm. More...
 
template<class Field >
void faddm (const Field &F, const FFLAS_TRANSPOSE transA, const FFLAS_TRANSPOSE transB, const size_t M, const size_t N, const typename Field::Element *A, const size_t lda, const typename Field::Element *B, const size_t ldb, typename Field::Element *C, const size_t ldc)
 faddm. More...
 
template<class Field >
void fsubm (const Field &F, const FFLAS_TRANSPOSE transA, const size_t M, const size_t N, const typename Field::Element *A, const size_t lda, typename Field::Element *B, const size_t ldb)
 fsubm. More...
 
template<class Field >
void fsubm (const Field &F, const FFLAS_TRANSPOSE transA, const FFLAS_TRANSPOSE transB, const size_t M, const size_t N, const typename Field::Element *A, const size_t lda, const typename Field::Element *B, const size_t ldb, typename Field::Element *C, const size_t ldc)
 fsubm. More...
 
template<class Field >
Field::Element * MatCopy (const Field &F, const size_t M, const size_t N, const typename Field::Element *A, const size_t lda)
 MatCopy makes a copy of the matrix M into a new allocated space. More...
 
size_t WinoSteps (const size_t m)
 Computes the number of recursive levels to perform. More...
 

Detailed Description

Finite Field Linear Algebra Subroutines

Author
Clément Pernet.

Function Documentation

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

Computes the threshold parameters for the cascade Matmul algorithm.

MatMulParameters.

Parameters
FFinite Field/Ring of the computation.
kCommon dimension of A and B, in the product A x B
betaComputing $AB + \beta C$
delayedDimReturns the size of blocks that can be multiplied over Z with no overflow
baseReturns the type of BLAS representation to use
winoRecLevelReturns the number of recursion levels of Strassen-Winograd's algorithm to perform
winoLevelProvidedtells whether the user forced the number of recursive level of Winograd's algorithm
Bibliography:
  • Dumas, Giorgi, Pernet, arXiv cs/0601133 here

Computes the threshold parameters for the cascade Matmul algorithm

Parameters
FFinite Field/Ring of the computation.
kCommon dimension of A and B, in the product A x B
betComputing AB + beta C
delayedDimReturns the size of blocks that can be multiplied over Z with no overflow
baseReturns the type of BLAS representation to use
winoRecLevelReturns the number of recursion levels of Strassen-Winograd's algorithm to perform
winoLevelProvidedtells whether the user forced the number of recursive level of Winograd's algorithm
size_t DotProdBound ( const Field &  F,
const size_t  w,
const typename Field::Element &  beta,
const FFLAS_BASE  base 
)
inline

Computes the maximal size for delaying the modular reduction in a dotproduct.

DotProdBound computes the maximal size for delaying the modular reduction in a dotproduct.

This is the default version assuming a conversion to a positive modular representation

Parameters
FFinite Field/Ring of the computation
winoRecLevelNumber of recusrive Strassen-Winograd levels (if any, 0 otherwise)
betaComputing AB + beta C
baseType of floating point representation for delayed modular computations

This is the default version assuming a conversion to a positive modular representation

Parameters
FFinite Field/Ring of the computation
wNumber of recusrive Strassen-Winograd levels (if any, 0 otherwise)
betaComputing AB + beta C
baseType of floating point representation for delayed modular computations
double computeFactorWino ( const Field &  F,
const size_t  w 
)
inline

Internal function for the bound computation.

Generic implementation for positive representations

FFLAS_BASE BaseCompute ( const Field &  F,
const size_t  w 
)
inline

Determines the type of floating point representation to convert to, for BLAS computations.

BaseCompute determines the type of floating point representation to convert to, for BLAS computations.

Parameters
FFinite Field/Ring of the computation
wNumber of recursive levels in Winograd's algorithm
size_t TRSMBound ( const Field &  F)
inline

Computes the maximal size for delaying the modular reduction in a triangular system resolution.

TRSMBound.

Compute the maximal dimension k, such that a unit diagonal triangular system of dimension k can be solved over Z without overflow of the underlying floating point representation.

Bibliography:
  • Dumas, Giorgi, Pernet 06, arXiv:cs/0601133.
Parameters
FFinite Field/Ring of the computation

computes the maximal size for delaying the modular reduction in a triangular system resolution

This is the default version over an arbitrary field. It is currently never used (the recursive algorithm is run until n=1 in this case)

Parameters
FFinite Field/Ring of the computation