M4RI-20100701 Release Notes

M4RI-20100701 was released on July 12th, 2010. 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, PLS 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+).

New in 20100701

Refactorisation

by Martin Albrecht

All mentions of LQUP were replaced with PLS which is what is actually computed by all functions formerly called "LQUP". The new files echelonform.c and echelonform.h provide high-level echelon forms in one place. This release thus breaks both source and binary compatibility with previous releases.

Heuristic Algorithm Choice for RREF

by Martin Albrecht

The function mzd_echelonize() will chose either M4RI or PLS based on the density of the input matrix. This choice is online such that as soon as the input matrix becomes dense enough during the execution of the M4RI algorithm the switch to PLS is performed. This increases performance on sparse-ish matrices. Please report performance regressions.

OpenMP Tuning and Fixes

by Martin Albrecht

M4RI's multicore performance was tuned using the 24 core sage.math machine. See http://martinralbrecht.wordpress.com/2010/06/08/m4ri-openmp-tuning/ for details.

Platforms

make check passes on the following platforms

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

The code also builds in Visual Studio under Windows.

M4RI-20100701 is included in and tested with Sage 4.5.