Allan Steel's Gröbner Basis Timings Page

On this page I present some Gröbner basis timings, gathered in May and August 2004.

80 Variable HFE Challenge 1 Solved by Magma in August 2004 here.

Magma V2.11 (first released in May 2004) has a new optimized implementation of the Faugère F4 algorithm. It performs very well, both over finite fields and over the rationals, as the following timings show.

The F4 algorithm is described in Jean-Charles Faugère's paper "A new efficient algorithm for computing Gröbner bases (F4)" .

Machine and Software Versions

For an accurate comparison, all timings are performed on an AMD Athlon XP 2800+ PC (2.087GHz), with cache sizes L1 64K, D 64K, L2 512K, 1.5GB main memory and running Redhat Linux 9.0 (kernel version 2.4.20-8). A few exceptions (requiring lots more memory) are noted below.

Software:

• Magma V2.11-8 (released in September 2004), which uses the new F4 algorithm.
• Magma V2.11-1 (released in May 2004), which uses the F4 algorithm. (V2.11-8 is an improved version of this.)
• Magma V2.10, which uses the Buchberger algorithm.
• Singular version 2-0-5, downloaded from here on April 28, 2004 (Buchberger algorithm).
• Macaulay 2 version 0.9.2, downloaded from here on May 13, 2004 (Buchberger algorithm).

All Gröbner bases are computed with respect to the grevlex (graded reverse lexicographical) order, and each software package is called with no special options, except for the HFE examples under Magma V2.11-8, for which the new special parameter HFE is given.

Magma computes the unique sorted reduced Gröbner basis for the term order, but the other systems seem not to do this by default. However, this is done very quickly by Magma, so I don't care about the extra bit that Magma has to do.

Timings are in seconds unless indicated otherwise. >T means that the computation was stopped after time T (and it was unclear how long there was to go). >>T means that the computation was stopped after time T when there was clearly a very long way to go (because the queue was very large and still growing).

I will add more systems, more examples, and the input for the examples as I get the time.

Modular (machine-short prime finite field)

All computations are over the prime finite field GF(32003). Magma actually handles prime finite fields up to GF(11863279) in the same time, but I restrict to this smaller prime for the other systems which handle small primes only up to 16 bits.

Singular clearly has a highly optimized Buchberger algorithm over small finite fields.

* For Cyclic 10 modulo p, the computation was done in 17.6 days in August 2004 on a 750MHz Sunfire v880. Only one sequential processor was used, and 30.7GB of memory was needed. The ideal is zero-dimensional, and the quotient of the polynomial ring by the ideal has dimension 34940 as a vector space. The largest step took 6.4 days and involved partially triangularizing a 544684 by 582742 matrix with density 1.3%. As far as I am aware, no-one else has successfully computed this Gröbner basis except for J.-C. Faugère, as explained in his F5 paper [ISSAC 2002], where he took 16 hours on a 1GHz PIII (using the unpublished improved F5' algorithm).

Rationals

All computations are over the rational field.

	Magma 2.11-8	Magma 2.11-1	Magma 2.10	Singular 2-0-5	Macaulay 2 0.9.2
Katsura 8	2.2	3.0	26.7	29.6	550.5
Katsura 9	12.2	28.2	291.2	800.0	6884.0
Katsura 10	130.7	266.3	4603.9	22972.2
Cyclic 7 (Hom)	2.2	2.2	51.1	5174.6	1649.5
Cyclic 8 (Hom)	83.7	134.8	4320.8	>>3 days	>2 days
Cyclic 9	4.6 days*	7.5 days*

* For Cyclic 9 over the rationals, the computation was done in 4.6 days in August 2004 (previously, 7.5 days in April 2004) on a 750MHz Sunfire v880. Only one sequential processor was used, and 11GB of memory was needed. As far as I am aware, no-one else has successfully computed this Gröbner basis except for J.-C. Faugère, as explained in his F4 paper. According to the paper (page 25), he took 18 days (sequential time) on three 200MHz x86 processors and one 400MHz Alpha processor. So the Magma timing is comparable (on one 750MHz processor).

GF(2)

All computations are over GF(2).

* For Cyclic 10 mod 2, the computation was done in 12.3 hours on a 750MHz Sunfire v880, using 9.3GB of memory. The ideal has dimension 4.

** Killed after about 10 hours because it was swapping very badly at 1.1GB and still growing with very many pairs to go.

Note to Magma users: from V2.11-8 onwards, you should set the HFE parameter to true for HFE inputs when calling Groebner or GroebnerBasis if the secret degree d is less than or equal to 127.

80 Variable HFE Challenge 1 Solved by Magma

In early August 2004 I solved the first HFE challenge of J. Patarin using Magma 2.11-8. This involves solving a system of 80 quadratic equations in 80 variables over GF(2). The input system can be downloaded from here. In October I made some small improvements for 2.11-9 which gives a speedup factor of about 1.1 to 1.2 over 2.11-8.

Magma 2.11-9 solves the system in 22.1 hours on a 750MHz Sunfire v880 (using 14.4GB of memory). You can see the Magma output for the run here. There are 4 solutions to the original equations, and the bulk of the computation involves partially triangularizing 3 moderately dense linear systems over GF(2), having respective dimensions 244097 by 1666981, 243493 by 1666981 and 293287 by 1666981.

The system was first solved by J.-C. Faugère using his F5/2 algorithm in May 2002 in 52.2 hours on a 1GHz Alpha EV68. (Thus, the Magma time is about 3 times faster [probably better than this, since the Alpha is a better 64-bit processor than the Sparc].)

I have also solved the system again on a Sun V20Z having an Opteron 248 processor (2.2GHz, 1MB L2 cache) and 8GB memory (only one sequential processor used). The computation takes 5.8 hours with V2.11-9 and uses 8.07GB. A special version of the algorithm is used which uses less memory (than the original 14.4GB) but is about 1.2 times slower.

I thank Geoff Bailey, Dan Bernstein and Alyson Reeves for several useful ideas, I thank Jean-Charles Faugère and Antoine Joux for providing me with HFE input systems, and I thank William Stein for use of his machines.

Last updated: October 22, 2004.