GBLA

Presentation

GBLA is an open source (GPLv2) C library for linear algebra specialized for eliminating matrices generated during Gröbner basis computations in algorithms like F4 or F5.

Download source

The sources of GBLA are accessible in different forms:

Current stable source (version 0.2).

In order to use it, you can proceed as follows : 
tar xf gbla-x.y.z.tar.gz
cd gbla-x.y.z
./autogen.sh
./configure
make

The configure step can be customised. Help is provided with configure --help and can be used like configure CFLAGS="-march=native -03" to replace default "-g -O2".

If you need the tools : 
cd tools ; make ;

Usage

Matrix database

Presentation

The goal is to share a large database of matrices occurring in Gröbner basis computations (to date mainly F4 and F5 algorithm) for benchmarking and testing purpose. Our matrix database lists matrices in two formats, described in [1]. The newer format matrices are suffixed by .gbm and are preferred for downloading since they are an order of magnitude smaller in disk space.
Both formats are usable in GBLA (don't forget the -n option for using the newer format). The newer format produces much lighter matrices; we list the other format for legacy reasons.

Browse the Matrix Database (726 matrices, 327GB of downloads).

Formats

The following table lists the elements in the binary format. The notation "b (32)" means that the first 32 bits represent element b. The notation "cols (nnz * 32) means that element cols spans over nnz*32 bits.
Old format New format
b (32)
m (32) m (32)
n (32) n (32)
nnz (64) nnz (64)
p (32) p (x)
data (nnz * x) rows (m * 32)
cols (nnz * 32) polmap (m * 32)
rows (m * 32) k (64)
colid (k * 64)
polynb (32)
polynnz (64)
polyrow (polynb * 32)
polydata (polynz * 32)
Numbering is zero based.
The header b contains information for the version of the format and the size "x" for the representation of the elemnents in the field. m and n are the number of rows and columns in the matrix, nnz is the number of non zero elements. p is the modulo. data lists the non zero elements in the matrix, read line by line from first in row to last. cols represents the column for the corresponding element in data. rows tells the size of each rows.
The new format compresses the field cols by finding consecutive column indices and compresses data by noting that many rows may share the same data (they are then a same polynomial shifted by several monomials).
polmap maps the data in a row to a number representing a polynomial in polydata. k is the size of the compressed colid. colid is the compression of cols: a single column is masked by (1<<32) while a sequence of s consecutive columns starting at col c is stored as "c s". polynb is the number of polynomials, polynnz is the total number of elements in these polynomials. polyrow is the lenght of each polynomial. polydata stores each polynomial coefficient in order from first to last.

Authors and Contacts

Bibliography

[1] B. Boyer, C. Eder, J.-C. Faugère, S. Lachartre, and F. Martani Improved Parallel Gaussian Elimination for Gröbner Bases Computations in Finite Fields preprint (n/a)
[2] J.-C. Faugère and S. Lachartre. Parallel Gaussian Elimination for Gröbner bases computations in finite fields. In M. Moreno-Maza and J. L. Roch, editors, Proceedings of the 4th International Workshop on Parallel and Symbolic Computation, PASCO ’10, pages 89–97, New York, NY, USA, July 2010. ACM. pdf
[3] S. Lachartre. Algèbre linéaire dans la résolution de systèmes polynomiaux Applications en cryptologie. PhD thesis, Université Paris 6, 2008. n/a
[4] F. Martani. Faugère-Lachartre Parallel Gaussian Elimination for Gröbner Bases Computations Over Finite Fields. Master's Thesis, Sorbonne Univerités, UMPC, 2012. pdf