**FFLAS-FFPACK
**

**Finite
field
linear algebra subroutines/package**

Or, how to have your computer doing linear algebra over finite fields almost as quickly as over double precision floating point numbers ?

[Presentation] | [Benchmarks] | [Documentation] | [Papers] | [Code] | [Contacts] |

This project consists in the creation of a set of
routines,
giving the same tools as a set of classical **Basic Linear Algebra
Subroutines**, but working over **finite fields**. In the same
way, some other routines of higher level (such as the one in LAPACK)
are also produced.

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

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

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 _{101}30.11 seconds4251.08 MffopsPentium4-2.4 GHz FFPACK LQUP factorization 7500*7500 Z _{101}103.00 seconds 2733.00 Mffops Pentium4-2.4 GHz

(in construction)

For further informations about this work, have 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

You can download the source code and use it under terms of the the GNU-LGPL license:

- http://linalg.org/projects/fflas-ffpack.
- FFLAS and FFPACK routines are also part of the LinBox
library (since version 0.2.0).

To run it, you need to link to a BLAS library. We give here some links to implementations of the BLAS:

- ATLAS for an automatically tuned BLAS, working on most common architectures. Installation may take a while.
- The GNU Scientific Library for a quick installation but quite poor efficiency.
- GotoBLAS: a very good alternative for efficiency on many modern architectures. But licence is limited to a personnal-academic use.

Installation: Simply untar the archive. This is a source library, so you just have to include the fflas.h or ffpack.h files in your programs.

To compile the tests:

- edit tests/Makefile
- set the path to your BLAS library and uncomment appropriate lines
- make

Please submit your questions, sugestions and bug reports to the discussion group ffpack-devel.

Clément PERNET Laboratoire d'Informatique de Grenoble, LIG, Université de Grenoble. 51, avenue Jean Kuntzmann, F-38330 Montbonnot Saint Martin, France. http://membres-liglab.imag.fr/pernet |
Pascal Giorgi Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier, LIRMM, Université de Montpellier. 161, rue Ada, F-34095, Montpellier, France. http://www.lirmm.fr/~giorgi |

Jean-Guillaume DUMAS Laboratoire Jean Kuntzmann LJK, Université de Grenoble. B.P. 53 -- 51, av. des Mathématiques, F-38041 Grenoble, France http://ljk.imag.fr/membres/Jean-Guillaume.Dumas |
Thierry GAUTIER Projet INRIA-MOAIS, Laboratoire Informatique et Distribution ZIRST - 51, av Jean Kuntzmann F-38330 Montbonnot Saint-Martin, France. http://moais.imag.fr/membres/thierry.gautier/TG/home_page.html |