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

Current stable source (version 0.0.3-r1).

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

Programme gbla
See usage for detailed help, and the following for a few examples.
Example:
```
zcat mat1.gz | ./gbla - 
```
Computes the eliminations, uses 1 thread, outputs nothing, uses the old format, reads from the gunzipped stream mat1.gz.
```
zcat matrices/mat1.gbm.gz | ./gbla -n -v 1 -t 4 - 
```
Computes the eliminations, uses 4 threads, outputs minimal information, uses the new format, reads from the gunzipped stream matrices/mat1.gbm.gz.
```
./gbla -v 2 -t 32 -n matrices/mat1.gbm 
```
Computes the eliminations, uses 32 threads, outputs timings and information, uses the new format, reads from a matrix mat1 on disk.
Binaries
Compiled binaries can be found there:
- linux (Intel static)
- linux (Intel AVX static)
Converter tools/converter
See usage. This tool converts from old format to new format and conversely. The new format saves up to an order of magnitude of space (see Matrix Database). This tool also enables sorting of the rows of the matrix by weight, playing on options -S, -s, -R, -r. By default, rows are sorted by largest weight first -r -s.
Example:
```
./converter mat1 > mat1.gbm
```
Converts a matrix in old format to a matrix in new format. A .gbm suffix is preferred for the new format.
```
zcat mat1.gz | ./converter -S -R - > mat1.gbm
```
This is the reading from stdin version. Also there is no sorting of the rows and no reversing.
Binaries
Compiled binaries can be found there:
- linux (Intel static)
- linux (Intel AVX static)
Exporter tools/dump_matrix
See usage. This tool exports a matrix in old or new format, from a file or an input stream, to Magma or SMS format (alike Matrix Market).
Example:
```
./dump_matrix mat1 
```
Outputs basic information on matrix mat1 to stdout
```
./dump_matrix -n -l matrices/mat1.gbm > matrices/mat1.sms
```
Create a SMS file matrices/mat1.sms from new format matrix matrices/mat1.gbm.
```
zcat mat1.gz | ./dump_matrix -m - > matrices/mat1.txt
```
Prints old-format matrix matrices/mat1.gz in Magma format on stdout.
Binaries
Compiled binaries can be found there:
- linux (Intel static)
- linux (Intel AVX static)

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 (542 matrices, 283GB 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)	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

B. Boyer
C. Eder
J.-C. Faugère
F. Martani

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

GBLA

Presentation

Download source

Usage

Programme gbla

Example:

Binaries

Converter tools/converter

Example:

Binaries

Exporter tools/dump_matrix

Example:

Binaries

Matrix database

Presentation

Formats

Authors and Contacts

Bibliography