Linalg

About FFLAS-FFPACK

FFLAS-FFPACK is a C++ linear algebra library. The FFLAS component contains BLAS-like routines for Z/pZ fields, while FFPACK, like LAPACK, implements algorithms for dense Z/pZ matrices and vectors.

Description

This project consists in the creation of a set of routines, giving similar tools as the set of classical Basic Linear Algebra Subroutines(matrix multiplication, triangular system solve...), but working over finite fields. In the same way, some other routines of higher level (such as the one in LAPACK) are also produced (LQUP factorization, Rank Det computation, Characteristic and minimal polynomial computation...).

The goal is to reach performances as close as possible to those of classical BLAS over double or float.

At this date, the work is split into two groups:

FFLAS (a BLAS interface for finite fields)
FFPACK (a higher level set of routines based on triangularizations)

Here are two examples of the performances attained by our package (speed is in Mffops = Millions of Finite Field operations per second):

Package	Exemple	Matrices Size	Field	Time	Speed	Processor
FFLAS	Multiplication of two dense matrices	4000*4000	Z₁₀₁	30.11 seconds	4251.08 Mffops	Pentium4-2.4 GHz
FFPACK	LQUP factorization	7500*7500	Z₁₀₁	103.00 seconds	2733.00 Mffops	Pentium4-2.4 GHz

Documentation

Benchmarks

We give more detailed timing comparisons of the library on several architectures. (in construction)

Bibliography

For further informations about this work, have may a look at:

Nov. 2008:Jean-Guillaume Dumas, Pascal Giorgi and Clément Pernet. Dense Linear Algebra over Finite Fields. ACM Transactions on Mathematical Software. Volume 35, n° 3, 34 pp.
Sept. 2006: Clément Pernet's PhD thesis: Algèbre linéaire exacte efficace: le calcul du polynome caractéristique
Dec. 2004: Pascal Giorgi's PhD thesis: Arithmetic and algorithmic in exact linear algebra for the LinBox library (in french)
July 2004: Our second preprint: FFPACK: Finite Field Linear Algebra Package. Jean-Guillaume Dumas, Pascal Giorgi and Clément Pernet. ISSAC'2004 : International Symposium on Symbolic and Algebraic Computations, Santander, España.
July 2004: Efficient dot product over finite fields. Jean-Guillaume Dumas CASC'2004 : Computer Algebra in Scientific Computing, Saint Petersburg, Russia.
April 2003: LUdivine: A Symbolic block LU factorisation for matrices over finite fields using BLAS. Morgan Brassel, Pascal Giorgi and Clément Pernet ECCAD'2003: East Coast Computer Algebra Day, , Clemson, South Carolina, USA.
July 2002: Our main preprint: Finite Field Linear Algebra Subroutines, (PPT). Jean-Guillaume Dumas, Thierry Gautier and Clément Pernet ISSAC'2002: International Symposium on Symbolic and Algebraic Computations, Lille, France.
June 2002: Morgan Brassel and Clément Pernet 's technical report: LUdivine: une divine factorisation LU, ( PPT in english, in french )
June 2001: Clément Pernet's technical report: Implementation of Winograd's Algorithm over Finite Fields using ATLAS level3 BLAS

Download

You can download the source code and use it under terms of the the GNU-LGPL2.1+ license:

http://linalg.org/projects/fflas-ffpack.

Contacts, Bugs, Wishes

please use our trac and mailing lists :

http://linalg.org/projects/fflas-ffpack.