Peformance

This page contains some benchmarking results for M4RI, MAGMA 2.14 , GAP 4.4 and NTL 5.4.2. It will be expanded in the future to contain more data on more operations. If you think that any result presented here is wrong and/or misleading, please let us know so that we can fix it.

Matrix Multiplication

Multiplying two random square matrices of the given dimension. GAP implements the M4RM algorithm, Magma implements Strassen-Winograd (on top of M4RM?) and M4RI implements Strassen-Winograd on top of M4RM.

64-bit Debian/GNU Linux, 2.33Ghz Core2Duo (Macbook Pro, 2nd Gen.)

Matrix Dimension	Magma 2.14-17 (64-bit)	GAP 4.4.10 (64-bit)	M4RI-20080821 (64-bit)
10,000 x 10,000	1.892	6.130	1.504
16,384 x 16,384	7.720	25.048	6.074
20,000 x 20,000	13.209	-	10.721
32,000 x 32,000	53.668	-	43.197

64-bit Debian/GNU Linux, 1.8Ghz Opteron (sage.math)

Matrix Dimension	Magma 2.13-5 (64-bit)	GAP 4.4.10 (64-bit)	M4RI-20080817 (64-bit)
10,000 x 10,000	3.875	21.421	3.845
16,384 x 16,384	14.999	91.202	16.541
20,000 x 20,000	27.203	-	26.584
32,000 x 32,000	101.677	-	103.885

64-bit Suse Linux, 2.4Ghz Opteron

Matrix Dimension	Magma 2.13-5 (64-bit)	GAP 4.4.10 (64-bit)	M4RI-20080521 (64-bit)
10,000 x 10,000	2.940	-	2.250
16,384 x 16,384	9.250	-	8.800
20,000 x 20,000	16.570	-	15.480
32,000 x 32,000	59.100	-	57.800

RHEL 5, 1.6Ghz Itanium

Matrix Dimension	Magma 2.14-16 (64-bit)	GAP 4.4.10 (64-bit)	M4RI-20080909 (64-bit)
10,000 x 10,000	7.941	-	4.200
16,384 x 16,384	31.046	-	16.430
20,000 x 20,000	55.654	-	28.830
32,000 x 32,000	209.483	-	109.414

Reduced Row Echelon Form

Computing the reduced row echelon form for random square matrices. Since these algorithms and implementations are sensitive to the structure of the input matrices (e.g. rank sensitive), benchmarks for random square matrices hold very little meaning (see for example this blog post) except maybe peak performance. We provide some more pratical examples below.

Note that the M4RI algorithm has worse theoretical time complexity when compared to the assymptotically fast matrix elimination implemented in Magma. However, the M4RI algorithm needs less memory: the 64,000 x 64,000 example below takes more than 2GB of memory in Magma but ~ 1GB with M4RI.

64-bit Debian/GNU Linux, 2.33Ghz Core2Duo (Macbook Pro, 2nd Gen.)

Matrix Dimension	Magma 2.14-17	NTL* 5.4.2	M4RI/M4RI 20090105	M4RI/PLUQ 20091101
10,000 x 10,000	2.474	14.14	1.532	0.864
16,384 x 16,384	7.957	67.52	6.597	3.602
20,000 x 20,000	13.151	123.70	12.031	6.138
32,000 x 32,000	39.653	462.32	40.768	25.290
64,000 x 64,000	251.346	2511.54	241.017	139.320

64-bit Debian/GNU Linux, 2.6Ghz Opteron (VMWare Virtualised)

Matrix Dimension	Magma 2.14-13	NTL* 5.4.2	M4RI/M4RI 20090105	M4RI/PLUQ 20091101
10,000 x 10,000	3.351	18.45	2.430	1.548
16,384 x 16,384	11.289	72.89	10.822	7.385
20,000 x 20,000	16.734	130.46	19.978	11.453
32,000 x 32,000	57.567	479.07	83.575	52.239
64,000 x 64,000	373.906	2747.41	537.900	306.02

RHEL 5, 1.6Ghz Itanium

Matrix Dimension	Magma 2.14-16	GAP 4.4.10	M4RI/M4RI 20080909	M4RI/PLUQ 20090617
10,000 x 10,000	8.069	-	3.418	2.410
16,384 x 16,384	25.828	-	19.987	12.720
20,000 x 20,000	43.256	-	30.829	15.800
32,000 x 32,000	157.134	-	118.121	65.550
64,000 x 64,000	892.481	-	874.609	342.680

(*) For GAP we call SemiEchelonMat which only returns the row echelon form not the reduced row echelon form. For NTL we call gauss which also doesn't return the reduced row echelon form.

The following timings are for matrices as they appear during a Gröbner basis computation for the HFE cryptosystem. These examples were provided by Michael Brickenstein. In input matrices are linked from the table below. To visualise the structure of the problem a scaled down version of the smallest input matrix follows:

64-bit Debian/GNU Linux, 2.6Ghz Opteron (VMWare Virtualised)

HFE (Filesize)	Matrix Dimension	Magma 2.14-13	M4RI/M4RI 20091101	M4RI/PLUQ 20091101
25 (5.6 MB)	12,307 x 13,508	4.79	3.61	4.408
30 (16 MB)	19,907 x 29,323	33.21	25.177	26.682
35 (40 MB)	29,969 x 55,800	278.58	144.389	162.110

The following timings are for matrices as they appear during a MutantXL computation. These examples were provided by Wael Said.

64-bit Debian/GNU Linux, 2.6Ghz Opteron (VMWare Virtualised)

Filesize	Matrix Dimension	Magma 2.15-12	M4RI/M4RI 20091101	M4RI/PLUQ 20091101
39 MB	26,407 x 26,075	79.730	24.101	19.093