M4RI-20110715 Release Notes

M4RI-20110715 was released on 11 July 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 20110715

Revised PLS Decomposition

The PLS decomposition algorithm was revised such that it never regresses to O(n^3) instead of O(n^3/log n). This improves performance for sparse-ish matrices. More details can be found in this blog post.

Improved cache tuning

The parameters for cache tuning were slightly improved such that it should run faster. Please report regressions.

Option to pass cache size values to configure

An option was added to configure to allow the user to pass values for L1:L2 cache sizes explicitly.

Supported Platforms

make check passes on the following platforms

• x86_64 Linux (sage.math.washington, redhawk.math.washington);
• x86 OSX (bsd.math.washington);
• ia64 Linux (iras.skynet);
• UltraSPARC T2 Solaris using GCC (t2.math.washington)
• x86 Linux (Pentium 4, cicero.skynet);

The code also builds in Visual Studio 10 under Windows.