M4RIE is a library for fast arithmetic with dense matrices over GF(2^e) for 2 ≤ e ≤ 16. The name stems from the fact that is relies heavily on M4RI. M4RIE is part of the Sage mathematics software. M4RIE is available under the General Public License Version 2 or later (GPLv2+).

Main Features

• basic arithmetic with dense matrices over GF(2^e) (addition, equality testing, stacking, augmenting, sub-matrices, etc.),

• asymptotically fast $O(n^{\log_2 7})$ matrix multiplication using the Karatsuba trick due to Boothby and Bradshaw,

• asymptotically fast $O(n^{\log_2 7})$ matrix multiplication using “Newton-John Table” based multiplication & the Strassen-Winograd algorithm,

• fast row echelon form computation and matrix inversion via a “Newton-John Table” based algorithm using only $O(n^2)$ field multiplications and $O(n^3)$ field additions,

• asymptotically fast row echelon form computation and matrix inversion via PLE decomposition,

• asymptotically fast TRiangular System solving with Matrices (upper left, lower left),

• support for Linux, OpenSolaris and OS X (all GCC).

See Further Reading for implemented algorithms.

Prerequisites

M4RIE depends heavily on M4RI.

Performance

See Performance.

Install

If you downloaded M4RI by cloning the mainline tree at

https://bitbucket.org/malb/m4ri

you need to first run the following command:

autoreconf --install

Then do the usual

./configure
make
make check

For details see the instructions in the file INSTALL.

Documentation

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/
doxygen

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/
make

The documentation is also available here.

Contributors

The following people have contributed to the M4RIE library.

• Martin Albrecht

We are grateful to William Stein for providing our hosting and general infrastructure in the past.

Citing M4RIE

If you use our libraries in a non-trivial part of your research please consider citing them as follows:

@manual{M4RI,
    key          = "M4RIE",
    author       = "Martin Albrecht",
    organization = "The M4RIE~Team",
    title        = "{The M4RIE Library -- Version **version**}",
    year         = **year**,
    url          = "\url{https://bitbucket.org/malb/m4rie}",
}

and cite the appropriate publications mentioned in Further Reading.

History

• 2020/01/25 A new version of M4RIE is available with a tiny distribution bugfix. It is available at https://bitbucket.org/malb/m4rie/downloads.

• 2020/01/15 A new version of M4RIE is available with a few small build system tweaks. It is available at https://bitbucket.org/malb/m4rie/downloads.

• 2015/09/08 A new version of M4RIE is available improving the build system and fixing a bug in the tests. It is available at https://bitbucket.org/malb/m4rie/downloads.

• 2015/04/17 Our hosting for http://m4ri.sagemath.org at University of Washington. is discontinued and we’re moving everything over to https://bitbucket.org/malb/m4ri. A copy of the old website (except for large files) is available at http://malb.bitbucket.org/m4ri-e-website-2008-2015/.

• 2014/09/14 A new version of M4RI and M4RIE is available for download. The biggest change is that A->offset was dropped. Also, various small (multicore) performance improvements were implemented. The update for M4RIE is to maintain compatibility with M4RI. A few improvements were implemented for the mzd_poly module as well.

• 2012/06/13 New versions of both M4RI and M4RIE are available for download. A detailed changlog are available here for M4RI.

• 2012/04/13 New versions of both M4RI and M4RIE are available for download. Detailed changlogs are available here for M4RI and here for M4RIE.

• 2011/12/04 New versions of both M4RI and M4RIE are available for download. The highlight of this version for M4RI is support for reading and writing 1-bit PNG images. The highlight of this release of M4RIE is much improved performance for $4 < e \leq 8$. Detailed changlogs are available here for M4RI and here for M4RIE.

• 2011/11/30 A technical report by Martin R. Albrecht is available describing the M4RIE library. In particular, Newton-John tables are introduced and our implementation of Karatsuba based matrix-matrix multiplication is described:

  The M4RIE library for dense linear algebra over small fields with even characteristic

  Abstract: In this work, we present the M4RIE library which implements efficient algorithms for linear algebra with dense matrices over GF(2^e) for 2 ≤ e ≤ 10. As the name of the library indicates, it makes heavy use of the M4RI library both directly (i.e., by calling it) and indirectly (i.e., by using its concepts). We provide an open-source GPLv2+ C library for efficient linear algebra over GF(2^e) for e small. In this library we implemented an idea due to Bradshaw and Boothby which reduces matrix multiplication over GF(p^k) to a series of matrix multiplications over GF(p). Furthermore, we propose a caching technique - Newton-John tables - to avoid finite field multiplications which is inspired by Kronrod's method ("M4RM") for matrix multiplication over GF(2). Using these two techniques we provide asymptotically fast triangular solving with matrices (TRSM) and PLE-based Gaussian elimination. As a result, we are able to significantly improve upon the state of the art in dense linear algebra over $F(2^e) with 2 ≤ e ≤ 10.