Wiki

Clone wiki

m4ri / M4RI-20090409

M4RI-20090409 Release Notes

M4RI-20090409 was released on April 9th, 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 20090409

Refactoring

by Martin Albrecht

This release breaks backward compatibility even more than usually. For instance, the packedmatrix type was renamed to mzd_t. Furthermore, its internal representation changed. The permutation structure was renamed to mzp_t.

Support for Large Matrices

by Martin Albrecht

Due to the refactored mzd_t type M4RI now supports matrices which are bigger than whatever a single malloc() system call can return. This allows to work with much bigger matrices than before.

As an example, we compute the rank of random matrices of dimensions 100000 x 100000, 200000 x 200000 and 256000 x 256000 on a Intel(R) Xeon(R) CPU X7460 @ 2.66GHz (geom.math):

sage: A = random_matrix(GF(2),10^5,10^5)
sage: %time A.echelon_form(algorithm='m4ri')
CPU times: user 1179.16 s, sys: 0.80 s, total: 1179.96 s
Wall time: 1179.96 s
100000 x 100000 dense matrix over Finite Field of size 2

sage: %time A.echelon_form(algorithm='pluq')
CPU times: user 427.59 s, sys: 1.73 s, total: 429.32 s
Wall time: 429.32 s
100000 x 100000 dense matrix over Finite Field of size 2
sage: A = random_matrix(GF(2),2*10^5,2*10^5)
sage: %time A.echelonize(algorithm='pluq')
CPU times: user 2282.97 s, sys: 15.33 s, total: 2298.30 s
Wall time: 2298.32 s
sage: A = random_matrix(GF(2),256*10^3,256*10^3)
sage: A
256000 x 256000 dense matrix over Finite Field of size 2
sage: %time A.echelonize(algorithm='m4ri',reduced=False)
CPU times: user 8977.43 s, sys: 1.90 s, total: 8979.33 s
Wall time: 8979.33 s

sage: %time A.echelonize(algorithm='pluq')
CPU times: user 3682.12 s, sys: 27.13 s, total: 3709.25 s
Wall time: 3709.26 s

New Strassen-Like Sequence for Multiplication and Squaring

by Marco Bodrato

A new sequence of commands was implemented which requires less additions for squaring than Strassen-Winograd. This provides a small speed-up in the ballpark of 1%. See [B08] for details.

[B08] Marco Bodrato. A Strassen-like matrix multiplication suited for squaring and highest power computation. Preprint N.622 Centro Interdipartimentale "Vito Volterra" - Università di Roma "Tor Vergata". http://bodrato.it/papers/#CIVV2008

Various Autoconf Issues Resolved

by Peter Jeremy

Various bugs in the cache detection routines were fixed. This allows to build M4RI on FreeBSD. However, we do not test M4RI on FreeBSD before each release (yet).

Other Changes

by Martin Albrecht

  • mzd_mul_naive() performance was improved
  • mzd_echelonize_m4ri() does not accept the parameters T and L} anymore, which were ignored before.
  • the documentation was improved to properly document return values.

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);

The code also builds in Visual Studio under Windows.

Updated