The Efficient Linear Algebra for Gröbner Basis Computations workshop in Kaiserslautern two weeks ago was a welcome opportunity to finally test out LELA, a library specifically written for linear algebra for Gröbner basis computations including for GF(2). The library implements the “Faugère-Lachartre” algorithm (a similar trick, though less developed, appeared before in PolyBoRi) and uses M4RI for dense parts over GF(2).
So, I ran my benchmark matrices through LELA, discovered a bug in the process, then Bradford returned the favour and discovered a bug in M4RI … Finally, below are the timings. The column PLE is the PLE algorithm as implemented in M4RI, M4RI is the M4RI algorithm as implemented in M4RI, GB is a very naive variant of the algorithm LELA uses and LELA is, well, LELA.
| problem | m | n | density | PLE | M4RI | GB | LELA |
| HFE 25 | 12307 | 13508 | 0.076 | 1.0 | 0.5 | 0.8 | 0.56 |
| HFE 30 | 19907 | 29323 | 0.067 | 4.7 | 2.7 | 4.7 | 3.42 |
| HFE 35 | 29969 | 55800 | 0.059 | 19.3 | 9.2 | 19.5 | 13.92 |
| Mutant | 26075 | 26407 | 0.184 | 5.7 | 3.9 | 2.1 | 12.07 |
| n=24, m=26 | 37587 | 38483 | 0.038 | 20.6 | 21.0 | 19.3 | 7.72 |
| n=24, m=26 | 37576 | 32288 | 0.040 | 18.6 | 28.4 | 17.0 | 4.09 |
| SR(2,2,2,4) c | 5640 | 14297 | 0.003 | 0.4 | 0.2 | 0.1 | 0.40 |
| SR(2,2,2,4) c | 13665 | 17394 | 0.013 | 2.1 | 3.0 | 2.0 | 1.78 |
| SR(2,2,2,4) c | 11606 | 16282 | 0.035 | 1.9 | 4.4 | 1.5 | 0.81 |
| SR(2,2,2,4) | 13067 | 17511 | 0.008 | 1.9 | 2.0 | 1.3 | 1.45 |
| SR(2,2,2,4) | 12058 | 16662 | 0.015 | 1.5 | 1.9 | 1.6 | 1.01 |
| SR(2,2,2,4) | 115834 | 118589 | 0.003 | 528.2 | 578.5 | 522.9 | 48.39 |
What this table means is that one can expect more than an order of magnitude of speed-up when using LELA – which is dedicated to these computations – instead of M4RI – which does not have the specialised algorithm implemented yet. For very small matrices sometimes M4RI/PLE win, but then not by a large margin. The only row where LELA doesn’t do so good is Mutant, which – btw. – is not an F4 matrix but comes from the MXL2 algorithm. It is possible that LELA’s sparse data structures are not that well equipped to deal with this rather dense matrix.
I am in the process of implementing the algorithm LELA uses in M4RI and will report updated timings here.
