Wiki
Clone wikim4ri / 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 improvedmzd_echelonize_m4ri()
does not accept the parametersT
andL}
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