About

M4RI is a library for fast arithmetic with dense matrices over $\mathbb{F}_2$. It was started by Gregory Bard, is maintained by Martin Albrecht. Several people contributed to it (see below). 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 is used by the Sage mathematics software and the PolyBoRi library. M4RI is available under the General Public License Version 2 or later (GPLv2+).

Features

Features of the M4RI library include:

basic arithmetic with dense matrices over $\mathbb{F}_2$ (addition, equality testing, stacking, augmenting, sub-matrices, randomisation, etc.),
asymptotically fast $O(n^{log_27})$ matrix multiplication via the “Method of the Four Russians” (M4RM) & Strassen-Winograd algorithm,
fast row echelon form computation and matrix inversion via the “Method of the Four Russians” (M4RI, $O(n^3/log(n))$),
asymptotically fast $O(n^{log_27})$ LQUP factorisation by reduction to matrix multiplication and the “Method of Many People Factorisation” (MMPF);
support for the x86/x86_64 SSE2 instruction set where available,
preliminary support for parallisation on shared memory systems via OpenMP and
support for Linux and OS X (GCC), Solaris 10 (Sun Studio Express) and Windows (Visual Studio 2008 Express and Cygwin).

We are working on improving the LQUP factorisation and better multi-core support.

Contributors

At least the following people have contributed to the M4RI library.

Tim Abbott: Debian-isation & advice on correct libtool versioning;
Martin Albrecht: maintainer, release manager, peformance tuning (M4RM, M4RI, Strassen, LQUP), initial M4RM implementation, parallelisation, LQUP factorisation (MMPF algorithm);
Gregory Bard: initial author, M4RI algorithm and initial implementation;
Marco Bodrato: new Strassen-like sequence for matrix multiplication and squaring which improves performance for squaring;
Michael Brickenstein: PolyBoRi author, standard conformity contributions for ANSIC, test data, discussion/suggestion of performance improvements, fast vector-matrix products;
Alexander Dreyer: PolyBoRi author, standard conformity contributions for ANSIC;
Jean-Guillaume Dumas: linear system resolution;
William Hart: many performance improvements for matrix multiplication and in general;
David Harvey: parallel parity function used in classical multiplication;
David Kirkby: portability issues (Solaris, HP Unix);
Clément Pernet: LQUP factorisation, triangular system solving (TRSM);
Wael Said: test cases, feedback;

We are thankful to William Stein for providing our hosting and general infrastructure.

News

2009/11/04 A new release is available for download. See the release notes for details.

2009/04/09 A new release is available for download. It heavily breaks backward compatibility but supports much bigger matrices than before. See the release notes for details.

2009/01/05 A new release is available for download. It contains new features, performance enhancements and bug fixes. Release notes are available in the wiki.

2008/11/12 A paper describing our matrix multiplication implementation is available as pre-print on the ArXiv. Also, M4RI is being packaged for Fedora Core. Finally, we updated the peformance data for GAP and Magma on the Core 2 Duo with improved timings.

2008/10/28 A new release is available for download. It contains mainly bugfixes but starting with this release triangular solving with matrices (TRSM) is fully supported. Also LUP factorisation (i.e. on full rank matrices) seems to be working now but it is not optimised at all.

2008/10/22 The slides for the Sage Days 10 talk about matrix multiplication in the M4RI library are available online.

2008/09/22 A new release is available. It is identical to the version of M4RI shipped with Sage 3.1.2 and contains many build fixes for a wide range of platforms. Sage (and thus M4RI) supportes x86 Linux, x86_64 Linux, ia64 Linux, x86 OSX and ppc OSX. M4RI also supports Windows and Solaris 10.

2008/08/26 This release is a pure bugfix release. Before this bugfix, if the input matrices were very non-square either wrong results or SIGSEGVs could be observed.

2008/08/21 A new release is available. This release contains Clément Pernet's latest LQUP and TRSM development code. LQUP still lacks a basecase but TRSM should be fairly complete. No attempts were made so far to optimise things. Furthermore, this release contains an improved strategy for choosing $k$ in M4RM which improves performance on the Core2Duo.

2008/08/17 A new release is available. This release adds a simple memory manager for systems with slow malloc/free syscalls. Also, the initialisation (m4ri_init) and finalisation (m4ri_fini) routines are now called automatically when the library is loaded/unloaded. This is tested with GCC and SunCC but not with MSVC. Matrix elimination got slightly faster across plattforms, multi-core support was extended to elimination and improved for multiplication. The README contains instruction how to enable multi-core support. This release does not contain Clément Pernet's latest LQUP patch.

2008/06/24 A new release is available. This release uses the libtool -release mechanism to ensure binary (in)compatibility between releases since - again - the API changed: since the project is quite young do not expect the API to be stable anytime soon. Also the new version attempts to detect the L1 and L2 cache sizes and uses a Strassen-Winograd cutoff by default such that both source matrices fit in L2 (this is not optimal but a good compromise). This new version has some scratch/experimental code which is the beginning of asymptotically fast LQUP factorisation. Finally, elimination got slightly faster.

2008/06/20 Thanks to Tim Abbott libM4RI is now in Debian/unstable.

2008/06/13 It turns out our comparison with Magma on the Core2Duo was strongly biased, since we compared with a version of Magma that was optimised for AMD64 rather than Intel64. The correct times are given now and we apologise for this mix-up.

2008/06/03 This release is a small bugfix release. Matrices are now printed correctly and a bug in mzd_gauss_delayed was reported and fixed by Wael Said and Mohammed Saied.

2008/06/01 This release greatly improves the performance of M4RI: the reduction of a given matrix to (reduced) row echelon form. The speed-up over the last release can be as much as ten, we will provide performance data for this in the near future. However, the new implementation still isn't asymptotically fast. Also mzd_transpose is much faster now due to improved data locality.

2008/05/21 Today's release fixes a severe bug found by Bill Hart, disables SSE2 on all CPUs except those manufactured by Intel (for performance reasons), improves performance on the Core2Duo and introduces a configure switch to enable OpenMP support.

2008/05/20 A new release is available with massive speed improvements for matrix multiplication. These improvements were discussed and tested in this thread on the [sage-devel] mailing list. This release has also experimental and preliminary support for OpenMP. To activate it compile with GCC 4.2 and

CFLAGS="-fopenmp -DHAVE_OPENMP"

Note however, that this release is still a developer preview since some automatic tuning is still not implemented, the performance on the Opteron isn't acceptable yet, and the parallel implementation is naive.

2008/05/16 Release early, release often. This release fixes the unconditional use of _mm_free even when it is not available.

2008/05/15 A new minor release is available which improves performance on Opterons. Also, the website has moved to http://m4ri.sagemath.org.

2008/05/10 Launch of this website.

Citing M4RI

If you use this library in a non-trivial part of your research please consider citing it as follows:

		@manual{M4RI,
		    key          = "M4RI",
		    author       = "Martin Albrecht and Gregory Bard"
		    organization = "The M4RI~Team",
		    title        = "{The M4RI Library -- Version 20080901}",
		    year         = 2008,
		    url          = "\url{http://m4ri.sagemath.org}",
		}

References for implemented algorithms can be found in the Further Reading section.

Contact

M4RI does not yet have a public mailinglist since we don't feel the need for it. If you like you can contact the maintainers directly at M.R.Albrecht_AT_rhul.ac.uk or bard_AT_fordham.edu.

M4RI - Linear Algebra over $\mathbb{F}_2$

Menu

Development

Links