wiki:WikiStart

FFLAS-FFPACK: Finite Field Linear Algebra Subroutines / Package

FFLAS-FFPACK is a LGPL-2.1+ source code library for basic linear algebra operations over a finite field. It is inspired by BLAS interface (Basic Linear Algebra Subprograms) and the LAPACK library for numerical linear algebra, and shares part of their design. Yet it differs in many aspects due to the specifities of computing over a finite field:

  • it is generic with respect to the finite field, so as to accomodate a large variety of field sizes and implementations;
  • it is a pure source code library, to be included and compiled in the user's software. Its build system is only used for tests and benchmarks.

Overview

FFLAS

FFLAS (Finite Field Linear Algebra Subprograms) provides the implementation of a subset of routines of the numerical BLAS, with the prefix letter `f standing for finite field.

  • fgemm : for the matrix multiplication of the form C = alpha . A x B + beta . C
  • trsm : for the triangular system solving with matrix right/left hand side: solving U x X = B for an unknown matrix X.
  • ftrmm : for the multiplication of a triangular matrix with a rectangular matrix. X = U x B
  • fger : for the outer product of two vectors: A = u x v^T + A
  • ...

Recently FFLAS started to also provide support for sparse matrix operations, more specifically sparse matrix vector product, using various data storage.

FFPACK

FFPACK (Finite Field Linear Algebra Package) is inspired by the LAPACK library to provide functionnalities of higher level, using the kernel of a BLAS. For the computations that are identical to the numerical linear algebra lirbary, the naming convention is kept:

  • fgetrs : solving a linear system using a LU decomposition;
  • ftrtri : inverting a triangular matrix;
  • ...

However the library also provides many other routines, specific to exact linear algebra:

  • RowEchelonForm : computing the row echelon form with or without the transformation matrix
  • CharPoly, MinPoly : computing the characteristic and minimal polynomials
  • Det, Rank, NullSpaceBasis : computing the determinant, the rank, a basis of the nullspace of a matrix.
  • ...

Downloads

Released 8/8/2014 fflas-ffpack-2.0.0.tar.gz  ChangeLog
Released 7/6/2012 fflas-ffpack-1.6.0.tar.gz  ChangeLog
Released 16/05/2012 fflas-ffpack-1.5.0.tar.gz  ChangeLog
Released 10/10/2011 fflas-ffpack-1.4.3.tar.gz  ChangeLog
Released 26/08/2011 fflas-ffpack-1.4.2.tar.gz  ChangeLog
Released 16/05/2011 fflas-ffpack-1.4.1.tar.gz  ChangeLog
Released 11/05/2011 fflas-ffpack-1.4.0.tar.gz  ChangeLog
Released 05/06/2008 fflas-ffpack-1.3.3.tar.gz  ChangeLog
Released 28/09/2007 fflas-ffpack-1.3.2.tar.gz  ChangeLog
Released 30/08/2007 fflas-ffpack-1.3.1.tar.gz  ChangeLog
Released 28/08/2007 fflas-ffpack-1.3.0.tar.gz  ChangeLog
Released 09/07/2007 fflas-ffpack-1.2.2.tar.gz  ChangeLog

You can also use the developer version by checking out the svn repository:

svn co svn://linalg.org/fflas-ffpack

Related Software

FFLAS-FFPACK depends on:

  • the givaro library  Givaro for implementations of finite fields, and a wrapping of  GMP multiprecision integers;
  • any implementation of a numerical BLAS library. We suggest using  OpenBLAS on most of nowadays computers.

FFLAS-FFPACK is used by:

  • the  LinBox linear algebra library for its dense linear algebra kernel,
  • the  SageMath open source computer algebra software.

(feel free to contact us if you are using FFLAS-FFPACK and want your project to be cited here).

Authors and credits

Authors

The FFLAS-FFPACK group is formed by the following authors:

  • Brice Boyer
  • Alexis Breust
  • Jean-Guillaume Dumas
  • Pascal Giorgi
  • Clément Pernet
  • Ziad Sultan
  • Bastien Vialla

Citing FFLAS-FFPACK

If your research depends on the FFLAS-FFPACK library, please consider citing the project as

@manual{fflas-ffpack,
  title = {{FFLAS-FFPACK}: {F}inite {F}ield {L}inear {A}lgebra {S}ubroutines / {P}ackage},
  author = {The FFLAS-FFPACK group},
  edition = {v2.0.0},
  year = {2014},
  note = {\url{http://linalg.org/projects/fflas-ffpack}}
}

Or you may also consider citing the related research article:

@article{DGP:2008,
  author = {Jean-Guillaume Dumas and Pascal Giorgi and Cl{\'e}ment Pernet},
  title = {Dense Linear Algebra over Word-Size Prime Fields: the FFLAS and FFPACK Packages},
  journal = {ACM Trans. on Mathematical Software (TOMS)},
  volume = {35},
  number = {3},
  year = {2008},
  issn = {0098-3500},
  pages = {1--42},
  doi = {10.1145/1391989.1391992},
  publisher = {ACM Press},
  address = {New York, NY, USA}
}

Contact

Use the  fflas-ffpack-devel discussion group for communication (bug reports, installation questions, feature requests, reports of successful applications, ...).