M4RI is a library for fast arithmetic with dense matrices over F2. It was started by Gregory Bard, is maintained by Martin Albrecht. Several people contributed to it. The name M4RI comes from the first implemented algorithm: The "Method of the Four Russians" inversion algorithm published by Gregory Bard. This algorithm in turn is named after the "Method of the Four Russians" multiplication algorithm which is probably better referred to as Kronrod's method. M4RI is used by the Sage mathematics software and the PolyBoRi library. M4RI is available under the General Public License Version 2 or later (GPLv2+).
Sage 4.1
| elim name='hfe25_5' algorithm='m4ri:' . 2.140
elim name='hfe30_5' algorithm='m4ri:' . 27.080
elim name='hfe35_5' algorithm='m4ri:' . 112.940
elim name='hfe25_5' algorithm='pluq:' . 2.680
elim name='hfe30_5' algorithm='pluq:' . 16.050
elim name='hfe35_5' algorithm='pluq:' . 83.380
elim name='mutant_matrix' algorithm='m4ri:' . 26.290
elim name='mutant_matrix' algorithm='pluq:' . 11.990
mul n=10000: . . . 1.450 1.463 1.480 1.480
mul n=16384: . . . 5.530 5.540 5.550 5.550
mul n=20000: . . . 10.430 10.433 10.440 10.440
mul n=32000: . . . 38.940 39.007 39.120 39.120
elim m=10000 n=10000 algorithm='m4ri:' . . . 1.660 1.690 1.710 1.710
elim m=16384 n=16384 algorithm='m4ri:' . . . 13.730 13.793 13.830 13.830
elim m=20000 n=20000 algorithm='m4ri:' . . . 27.100 27.103 27.110 27.110
elim m=32000 n=32000 algorithm='m4ri:' . . . 95.870 95.917 95.990 95.990
elim m=10000 n=10000 algorithm='pluq:' . . . 0.870 0.873 0.880 0.880
elim m=16384 n=16384 algorithm='pluq:' . . . 5.610 5.697 5.860 5.860
elim m=20000 n=20000 algorithm='pluq:' . . . 5.970 5.980 5.990 5.990
elim m=32000 n=32000 algorithm='pluq:' . . . 24.560 24.573 24.590 24.590
elim m=10000 n=20000 algorithm='m4ri:' . . . 9.170 9.187 9.210 9.210
elim m=16384 n=32768 algorithm='m4ri:' . . . 43.680 43.837 44.030 44.030
elim m=20000 n=40000 algorithm='m4ri:' . . . 80.490 80.563 80.620 80.620
elim m=32000 n=64000 algorithm='m4ri:' . . . 229.350 229.570 229.960 229.960
elim m=10000 n=20000 algorithm='pluq:' . . . 3.020 3.037 3.050 3.050
elim m=16384 n=32768 algorithm='pluq:' . . . 15.470 15.510 15.580 15.580
elim m=20000 n=40000 algorithm='pluq:' . . . 20.840 20.867 20.890 20.890
elim m=32000 n=64000 algorithm='pluq:' . . . 69.020 69.130 69.190 69.190
|
r297
| elim name='hfe25_5' algorithm='m4ri:' . 2.200
elim name='hfe30_5' algorithm='m4ri:' . 27.070
elim name='hfe35_5' algorithm='m4ri:' . 111.480
elim name='hfe25_5' algorithm='pluq:' . 2.130
elim name='hfe30_5' algorithm='pluq:' . 13.120
elim name='hfe35_5' algorithm='pluq:' . 71.760
elim name='mutant_matrix' algorithm='m4ri:' . 26.300
elim name='mutant_matrix' algorithm='pluq:' . 8.650
mul n=10000: . . . 1.460 1.483 1.520 1.520
mul n=16384: . . . 5.580 5.590 5.600 5.600
mul n=20000: . . . 10.480 10.487 10.500 10.500
mul n=32000: . . . 38.890 38.973 39.050 39.050
elim m=10000 n=10000 algorithm='m4ri:' . . . 1.700 1.727 1.770 1.770
elim m=16384 n=16384 algorithm='m4ri:' . . . 13.740 13.900 14.180 14.180
elim m=20000 n=20000 algorithm='m4ri:' . . . 27.080 27.100 27.120 27.120
elim m=32000 n=32000 algorithm='m4ri:' . . . 95.220 95.750 96.090 96.090
elim m=10000 n=10000 algorithm='pluq:' . . . 0.740 0.787 0.810 0.810
elim m=16384 n=16384 algorithm='pluq:' . . . 3.140 3.290 3.370 3.370
elim m=20000 n=20000 algorithm='pluq:' . . . 5.560 5.563 5.570 5.570
elim m=32000 n=32000 algorithm='pluq:' . . . 23.230 23.253 23.270 23.270
elim m=10000 n=20000 algorithm='m4ri:' . . . 9.160 9.177 9.200 9.200
elim m=16384 n=32768 algorithm='m4ri:' . . . 43.600 43.797 44.070 44.070
elim m=20000 n=40000 algorithm='m4ri:' . . . 80.320 80.387 80.440 80.440
elim m=32000 n=64000 algorithm='m4ri:' . . . 229.820 231.157 233.630 233.630
elim m=10000 n=20000 algorithm='pluq:' . . . 2.940 2.950 2.960 2.960
elim m=16384 n=32768 algorithm='pluq:' . . . 12.120 12.163 12.230 12.230
elim m=20000 n=40000 algorithm='pluq:' . . . 20.010 20.023 20.040 20.040
elim m=32000 n=64000 algorithm='pluq:' . . . 65.640 65.760 65.940 65.940
|
r297 + hybrid patch
| elim name='hfe25_5' algorithm='heuristic:' . 1.980
elim name='hfe30_5' algorithm='heuristic:' . 13.130
elim name='hfe35_5' algorithm='heuristic:' . 71.760
elim name='hfe25_5' algorithm='pluq:' . 2.130
elim name='hfe30_5' algorithm='pluq:' . 13.080
elim name='hfe35_5' algorithm='pluq:' . 71.480
elim name='mutant_matrix' algorithm='heuristic:' . 8.800
elim name='mutant_matrix' algorithm='pluq:' . 8.600
mul n=10000: . . . 1.460 1.487 1.540 1.540
mul n=16384: . . . 5.590 5.610 5.620 5.620
mul n=20000: . . . 10.450 10.473 10.490 10.490
mul n=32000: . . . 38.960 38.980 39.000 39.000
elim m=10000 n=10000 algorithm='heuristic:' . . . 0.760 0.797 0.820 0.820
elim m=16384 n=16384 algorithm='heuristic:' . . . 3.090 3.207 3.370 3.370
elim m=20000 n=20000 algorithm='heuristic:' . . . 5.580 5.583 5.590 5.590
elim m=32000 n=32000 algorithm='heuristic:' . . . 23.330 23.337 23.350 23.350
elim m=10000 n=10000 algorithm='pluq:' . . . 0.750 0.767 0.800 0.800
elim m=16384 n=16384 algorithm='pluq:' . . . 3.310 3.333 3.350 3.350
elim m=20000 n=20000 algorithm='pluq:' . . . 5.550 5.557 5.570 5.570
elim m=32000 n=32000 algorithm='pluq:' . . . 23.260 23.273 23.290 23.290
elim m=10000 n=20000 algorithm='heuristic:' . . . 2.940 2.940 2.940 2.940
elim m=16384 n=32768 algorithm='heuristic:' . . . 12.080 12.230 12.390 12.390
elim m=20000 n=40000 algorithm='heuristic:' . . . 19.970 20.000 20.020 20.020
elim m=32000 n=64000 algorithm='heuristic:' . . . 65.300 65.903 66.380 66.380
elim m=10000 n=20000 algorithm='pluq:' . . . 2.910 2.917 2.930 2.930
elim m=16384 n=32768 algorithm='pluq:' . . . 12.050 12.093 12.170 12.170
elim m=20000 n=40000 algorithm='pluq:' . . . 19.960 19.963 19.970 19.970
elim m=32000 n=64000 algorithm='pluq:' . . . 65.210 65.333 65.580 65.580
|
This revision is from 2009-11-03 13:37
