M4RI and Structured Matrices

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.

64-bit Debian/GNU Linux, 2.6Ghz Opteron (VMWare Virtualised)
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
64-bit Fedora Linux, 2.33Ghz Xeon (eno)
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
64-bit Ubuntu Linux, 2.66Ghz Xeon (sage.math)
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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s