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]

[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:

• 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	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

FFLAS

The core of the FFLAS library is the matrix matrix multiplication routine. It's main characteristics are

Here again, the performances are very good: A 7500*7500 matrix is factorized in 103 seconds with a speed of 2733 Mops on a P4-2.4Ghz.
See here also the performances obtained for rank computations :


For comparison, the numerical  LUP factorization of a 3000*3000 matrix using Lapack spends 6 seconds whereas our version over finite fields needs 8.5 seconds.

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

• June 2001: Clément Pernet's technical report: Implementation of Winograd's Algorithm over Finite Fields using ATLAS level3 BLAS
• June 2002: Morgan Brassel and Clément Pernet 's technical report: LUdivine: une divine factorisation LU, ( PPT in english, in french )
• August 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, 7-10 Juillet 2002, Lille, France.
• 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, April 5^th 2003, Clemson, South Carolina, USA.
• July 2004: Efficient dot product over finite fields.
  Jean-Guillaume Dumas
  CASC'2004 : Computer Algebra in Scientific Computing, 12-19 Juillet 2004, Saint Petersburg, Russia.
• 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, 4-7 Juillet 2004, Santander, España.
  
• Sept. 2006: Clément Pernet's PhD thesis: Algèbre linéaire exacte efficace: le calcul du polynome caractéristique
  
  

 

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

• fflas-ffpack-1.3.1.tar.gz: 30/08/2007. (ChangeLog)
• fflas-ffpack-1.3.0.tar.gz: 28/08/2007. (ChangeLog)
• fflas-ffpack-1.2.2.tar.gz: 09/07/2007. (ChangeLog)
• fflas-ffpack-1.2.1.tar.gz: 21/06/2007. (ChangeLog)
• fflas-ffpack-1.1.2.tar.gz: 14/03/2007. (ChangeLog)
• fflas-ffpack-1.1.1.tar.gz: 13/03/2007. (ChangeLog)
• fflas-ffpack-1.1.0.tar.gz: 27/02/2007. (ChangeLog)
• fflasffpack-1.0.1.tar.gz: 13/08/2006. (ChangeLog)
• fflasffpack-1.0.tgz: the package, including the FFLAS-FFPACK routines ( matrix multiplication, triangular system solve, LQUP factorization, Rank Det computation, Characteristic and minimal polynomial computation...).
• 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 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