I have blogged before about the issues we face in M4RI if the matrices we work with are relatively sparse. In a nutshell, computing the, say, row echelon form of these matrices may take *longer* than for random matrices. In particular, all the nice work we’ve done for making matrix elimination fast M4RI might not pay off for the kind of matrices I care about such as matrices as they appear when computing Gröbner bases for relatively dense systems of polynomials in PolyBoRi. A few examples of such matrices can be downloaded from the M4RI performance site. Since I am writing up my thesis (and Clément and I are working on a joint paper) I played around with a simple hybrid algorithm today. The idea is simple: M4RI is faster for sparse-ish matrices than PLS decomposition mainly due to the lack of column swaps. Thus, run M4RI until the density of the remaining matrix is above a certain threshold and then switch to the PLS-based approach. It turns out this works reasonably well for the benchmark matrices.

Problem (Filesize) | Matrix Dimension |
Density | Magma 2.14-13 |
M4RI 20100324 |
PLS 20100324 |
M+P 0.15 20100414 |
M+P 0.20 20100414 |
---|---|---|---|---|---|---|---|

HFE 25 (5.6 MB) | 12,307 x 13,508 | 0.076 | 4.57s | 3.28s | 3.45s | 3.44s | 3.08 |

HFE 30 (16 MB) | 19,907 x 29,323 | 0.067 | 33.21s | 23.72s | 25.42s | 22.79s | 20.71 |

HFE 35 (40 MB) | 29,969 x 55,800 | 0.059 | 278.58s | 126.08s | 159.72s | 121.03s | 123.75 |

MXL2 (39MB) | 26,075 x 26,407 | 0.185 | 76.81s | 23.03s | 19.04s | 18.31s | 17.15 |

Problem (Filesize) | Matrix Dimension |
Density | Magma 2.16-7 |
M4RI 20100324 |
PLS 20100324 |
M+P 0.15 20100414 |
M+P 0.20 20100414 |
---|---|---|---|---|---|---|---|

HFE 25 (5.6 MB) | 12,307 x 13,508 | 0.076 | 3.68s | 1.94s | 2.09s | 2.16s | 1.92 |

HFE 30 (16 MB) | 19,907 x 29,323 | 0.067 | 23.39s | 11.46s | 13.34s | 11.37s | 10.60 |

HFE 35 (40 MB) | 29,969 x 55,800 | 0.059 | — | 49.19s | 68.85s | 53.17s | 47.90 |

MXL2 (39MB) | 26,075 x 26,407 | 0.185 | 55.15 | 12.25s | 9.22s | 9.09s | 9.25 |

Problem (Filesize) | Matrix Dimension |
Density | M4RI 20100324 |
PLS 20100324 |
M+P 0.15 20100414 |
M+P 0.20 20100414 |
---|---|---|---|---|---|---|

HFE 25 (5.6 MB) | 12,307 x 13,508 | 0.076 | 2.24s | 2.00s | 2.25s | 2.04 |

HFE 30 (16 MB) | 19,907 x 29,323 | 0.067 | 27.52s | 13.29s | 11.75s | 13.39 |

HFE 35 (40 MB) | 29,969 x 55,800 | 0.059 | 115.35s | 72.70s | 54.97s | 111.27 |

MXL2 (39MB) | 26,075 x 26,407 | 0.185 | 26.61s | 8.73s | 8.82s | 10.32 |

In the above *M+P* denotes the hybrid hack and the number following M+P is the switch-over density. Clearly, this simple strategy does not always give optimal results, but it does indeed look promising at least for some (relevant) applications. I did not commit the patch however, since it is too much of a hack. We will have think whether and how to incorporate it properly. Btw. I don’t have access to Magma on sage.math.