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.
