M4RI-20090105 Release Notes

M4RI-20090105 was released on January 5th, 2009. 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, PLUQ factorisation 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 20080105

Asymptotically Fast PLUQ Factorisation [mzd_pluq() and _mzd_pluq_mmpf()]

by Clément Pernet and Martin Albrecht

Asymptotically PLUQ factorisation of matrices was implemented which provides asymptotically fast rank computation, row echelon forms and rank profiles. The implementation is not fully optimised yet. While it is faster than M4RI for dense (random) matrices it is slower than M4RI for sparse-ish and structured matrices.

System Solving [mzd_solve_left()]

by Jean-Guillaume Dumas

A high-level wrapper around the PLUQ and TRSM routines to provide linear system solving.

M4RI Performance Improvement [mzd_echelonize_m4ri()]

by Martin Albrecht

A bug was fixed in M4RI which resulted in poor performance of M4RI for sparse-ish matrices.

Other Changes

by Martin Albrecht, Michael Brickenstein, Jean-Guillaume Dumas and Clément Pernet

• mzd_mul_m4rm_t() was removed
• new m4ri_random_word(): returns a random word
• new mzd_density(): returns the density of a matrix
• new mzd_mul_va(): v*A for v a vector and A a matrix
• new mzp_print(): prints a permutation
• new mzd_is_zero(): returns true if a matrix is zero
• mzd_reduce_m4ri() renamed to mzd_echelonize_m4ri()
• mzd_reduce_naiv() renamed to mzd_echelonize_naive()
• mzd_print_matrix() renamed to mzd_print()
• new make test target
• increased test suite coverage

License Clarification

by Martin Albrecht

Each source file's license statement was clarified to GPLv2+.

Platforms

make check passes on the following platforms

• x86_64 Linux (Core2Duo, sage.math);
• x86 OSX (Core2Duo, bsd);
• ia64 Linux (Itanium, iras);
• x86 Linux (VirtualBox);
• x86 OpenSolaris (VirtualBox).

The code also builds in Visual Studio under Windows.