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]

Jean-Guillaume Dumas


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 Z101 30.11 seconds 4251.08 Mffops Pentium4-2.4 GHz
FFPACK LQUP factorization 7500*7500 Z101 103.00 seconds 2733.00 Mffops Pentium4-2.4 GHz

Jean-Guillaume Dumas


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



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


Jean-Guillaume Dumas

[Source Code]

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

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


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:
Jean-Guillaume Dumas


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.

Pascal Giorgi
Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier,
LIRMM, Université de Montpellier.
161, rue Ada,
F-34095, Montpellier, France.

Jean-Guillaume DUMAS
Laboratoire Jean Kuntzmann
LJK, Université de Grenoble.
B.P. 53 -- 51, av. des Mathématiques,
F-38041 Grenoble, France

Projet INRIA-MOAIS, Laboratoire Informatique et Distribution
ZIRST - 51, av Jean Kuntzmann
F-38330 Montbonnot Saint-Martin, France.




Valid HTML 4.01!