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 Russian"” 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
M4RI is available at http://m4ri.sagemath.org
* basic arithmetic with dense matrices over F2 (addition, equality
testing, stacking, augmenting, sub-matrices, randomisation);
* asymptotically fast O(n^log_2(7)) matrix multiplication via the "Method
of the Four Russians" (M4RM) & Strassen-Winograd algorithm;
* asymptotically fast O(n^log_2(7)) PLE factorisation (Gaussian
elimination, system solving, ...);
* fast row echelon form computation and matrix inversion via the "Method
of the Four Russians" (M4RI, O(n^3/log(n)));
* support for the x86/x86_64 SSE2 instruction set where available;
* preliminary support for parallelisation on shared memory systems
* and support for Linux, Solaris, and OS X (GCC) and limited support
for Windows (Visual Studio 2010).
OpenMP support for parallel multiplication and elimination is enabled
configure switch. If GCC is used to compile the library it is advised
to use at least GCC 4.3 since earlier versions have problems with
OpenMP in shared libraries. OpenMP support was introduced in GCC
4.2. Both MSVC and SunCC support OpenMP but we have no experience with
Generally speaking better performance improvements can be expected on
multi-core AMD CPUs than on multi-core Intel CPUs. This is because the
later has a shared L2 cache which is already almost fully utilised in
the single-core implementation.
Overall, the speed-up is considerably but sublinear. See
If you downloaded M4RI as a compressed tarball from its website,
installation instructions are contained in the file INSTALL. If you
downloaded M4RI by cloning the mainline tree at
you need to first run the following command:
$ autoreconf --install
Then follow the instructions in the file INSTALL.
To build the reference manual, ensure that you have Doxygen installed.
The HTML version of the reference manual can be built as follows:
$ cd src/
The built documentation is contained under the doc subdirectory of m4ri/.
Once the HTML version is built, you can build the PDF version as follows:
$ cd doc/latex/