Two days ago I wrote about LELA’s implementation of Gaussian elimination for Gröbner basis computations over . Yesterday, I implemented LELA’s algorithm (which is from Faugere & Lachartre paper) in M4RI. Continue reading “Linear Algebra for Gröbner Bases over GF(2): M4RI”

# Tag: lela

## Linear Algebra for Gröbner Bases over GF(2): LELA

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.