M4RI-20110601 Release Notes

M4RI-20110601 was released on 30 May 2011. It is available at:

http://m4ri.sagemath.org/downloads/

About M4RI

M4RI is a library for fast arithmetic with dense matrices over F2. 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 implements asymptotically fast matrix multiplication, linear system solving, reduced row echelon forms, PLE decomposition and basic arithmetic. 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+).

Changes in 20110601

Note: This version breaks compatibility with previous versions. In most cases simply recompiling against this new version should be sufficient. However, if third party code reaches into the internals of the library, it might require adaptation.

Faster Column Swaps

by Carlo Wood

Column swaps are now considerably faster.

Old Code

./bench_packedmatrix mzd_col_swap 64 64 1 17
Total running time:  3.646 seconds.
Sample size: 136; mean: 456.2; standard deviation: 20.3
99% confidence interval: +/- 4.5 (1.0%): [451.7..460.8]
function: mzd_col_swap, count: 156250, m: 64, n: 64, cola: 1, colb: 17, 
wall time: 0.171514 us, cpu cycles: 456, cc/m: 7.128807

./bench_packedmatrix mzd_col_swap 10000 10000 1 7182
Total running time: 28.364 seconds.
Sample size: 198; mean: 264278; standard deviation: 14315
99% confidence interval: +/- 2637 (1.0%): [261641..266916]
function: mzd_col_swap, count: 1000, m: 10000, n: 10000, cola: 1, colb: 7182, 
wall time: 0.099348 ms, cpu cycles: 264278, cc/m: 26.427831

20110601

./bench_packedmatrix mzd_col_swap 64 64 1 17
Total running time:  6.916 seconds.
Sample size: 447; mean: 263.2; standard deviation: 21.6
99% confidence interval: +/- 2.6 (1.0%): [260.6..265.9]
function: mzd_col_swap, count: 156250, m: 64, n: 64, cola: 1, colb: 17, 
wall time: 0.098963 us, cpu cycles: 263, cc/m: 4.113206

./bench_packedmatrix mzd_col_swap 10000 10000 1 7182
Total running time: 16.878 seconds.
Sample size: 141; mean: 197454; standard deviation: 8929
99% confidence interval: +/- 1961 (1.0%): [195493..199416]
function: mzd_col_swap, count: 1000, m: 10000, n: 10000, cola: 1, colb: 7182, 
wall time: 0.074228 ms, cpu cycles: 197454, cc/m: 19.745422

Faster Transpose

by Carlo Wood

Transposing a matrix is now much much faster than in previous versions of M4RI. Considerable effort went into this. The code provides a good case study how much care has to be taken to achieve good performance.

Old Code

function: mzd_transpose, count: 9765, m: 32, 
wall time: 1.583922 us, cpu cycles: 4213, cc/m^2: 4.114724

function: mzd_transpose, count: 9182, m: 33, 
wall time: 1.654324 us, cpu cycles: 4401, cc/m^2: 4.041117

function: mzd_transpose, count: 2441, m: 64, 
wall time: 5.282671 us, cpu cycles: 14052, cc/m^2: 3.430777

function: mzd_transpose, count: 2366, m: 65, 
wall time: 5.813187 us, cpu cycles: 15464, cc/m^2: 3.660125

function: mzd_transpose, count: 610, m: 128, 
wall time: 2.327869 us, cpu cycles: 6193, cc/m^2: 0.378011

function: mzd_transpose, count: 271, m: 192, 
wall time: 0.030325 ms, cpu cycles: 80661, cc/m^2: 2.188073

function: mzd_transpose, count: 252, m: 199, 
wall time: 0.059583 ms, cpu cycles: 158497, cc/m^2: 4.002360

function: mzd_transpose, count: 152, m: 256, 
wall time: 0.011204 ms, cpu cycles: 29799, cc/m^2: 0.454693

20110601

function: mzd_transpose, count: 9765, m: 32, n: 32, 
wall time: 0.163236 us, cpu cycles: 434, cc/mn: 0.423901

function: mzd_transpose, count: 9182, m: 33, n: 33, 
wall time: 0.538445 us, cpu cycles: 1432, cc/mn: 1.315113

function: mzd_transpose, count: 2441, m: 64, n: 64, 
wall time: 0.490782 us, cpu cycles: 1305, cc/mn: 0.318607

function: mzd_transpose, count: 2366, m: 65, n: 65, 
wall time: 0.593829 us, cpu cycles: 1579, cc/mn: 0.373811

function: mzd_transpose, count: 610, m: 128, n: 128, 
wall time: 1.621311 us, cpu cycles: 4314, cc/mn: 0.263277

function: mzd_transpose, count: 271, m: 192, n: 192, 
wall time: 3.712177 us, cpu cycles: 9871, cc/mn: 0.267780

function: mzd_transpose, count: 252, m: 199, n: 199, 
wall time: 4.345238 us, cpu cycles: 11557, cc/mn: 0.291831

function: mzd_transpose, count: 152, m: 256, n: 256, 
wall time: 6.440789 us, cpu cycles: 17124, cc/mn: 0.261287

Faster Addition

by Martin Albrecht

The previous addition code was very badly written which made addition very slow for small matrices. this version fixes this issue.

Improved Benchmarketing Tools

by Carlo Wood

All benchmarking programs now provide much more accurate data, using appropriate statistical modelling to give a confidence interval.

Usage

 * Example usage:
 *
 * ./bench_elimination -s 0 -m 4 -c 90 -a 0.005 -d -t 30 -n 1000 1000 1000
 *
 * would run at most 30 seconds (-t) or 1000 times (-n), whichever comes
 * first, or stop after the real average of wall time (-s 0) falls with 90%
 * certainty (-c) in a range that is +/- 0.005 times the observed mean (-a: accuracry),
 * but no sooner than that at least 4 (-m: minimum) measurements have been
 * done. It would also print (-d: dump) each measurement (0:microseconds 1:cpuclocks).

Example

/bench_elimination -t 180 -c 95 10000 10000 m4ri 5000 # max run. time: 180 secs, confidence: 95%
.......
Total running time: 18.483 seconds.
Sample size: 7; mean: 1916541669; standard deviation: 19560954
95% confidence interval: +/- 18091517 (0.9%): [1898450152..1934633186]
m: 10000, n: 10000, last r:  5000, cpu cycles: 1916541669, wall time: 0.720465

Furthermore, it is now possible to gather benchmarking information such as cache misses. For this feature the PAPI library is required.

Swapped Internal Bit-representation

by Carlo Wood

Bit zero is now at index zero instead of at index RADIX-1.

This breaks compatibility with previous versions.

New Matrix Layout

by Carlo Wood

Our matrix layout was improved to allow looping over matrix rows without address lookups for each row.

This breaks compatibility with previous versions.

TRSM Upper Left using Greasing

by Martin Albrecht

Improved TRSM upper left code by explicitly using greasing, cf., http://martinralbrecht.wordpress.com/2010/11/19/trsm-with-greasing-trsm-reduced-to-matrix-multiplication/.

New Configure Options --enable-debug-mzd and --enable-debug-dump

by Carlo Wood

• debug-mzd runs a series of consistency checks on matrices at the end of function calls.
• debug-dump prints a hash of all matrices at the end of a function call. This allows to spot regressions quicker (by comparing hashs)

Improved Configure Scripts

by Carlo Wood

Our configure scripts saw an overhaul which should make them more standard conforming.

Supported Platforms

make check passes on the following platforms

• x86_64 Linux (sage.math, redhawk);
• x86 OSX (Xeon, bsd);
• x86 Linux (VirtualBox);
• UltraSPARC T2 Solaris using GCC (t2.math.washington.edu)
• ia64 Linux (iras);

The code also builds in Visual Studio 10 under Windows.