Bitbucket is a code hosting site with unlimited public and private repositories. We're also free for small teams!

Close
INTRODUCTION
============

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
Kronrod's method.

M4RI is available at http://m4ri.sagemath.org

FEATURES
========

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

 * fast row echelon form computation and matrix inversion via the "Method
   of the Four Russians" (M4RI, O(n^3/log(n)));

 * asymptotically fast PLUQ factorisation;

 * support for the x86/x86_64 SSE2 instruction set where available;

 * preliminary support for parallelisation on shared memory systems via
   OpenMP;

 * and support for Linux and OS X (GCC), support for Solaris (Sun
   Studio Express) and support for Windows (Visual Studio 2008 Express).

OPENMP SUPPORT
==============
OpenMP support for parallel multiplication and elimination is enabled
with the

  --enable-openmp

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
these yet.

Generally speaking better performance improvements can be expected on
dual-core Opteron CPUs than on dual-core Core2Duo 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

  http://m4ri.sagemath.org/performance.html

for details.

INSTALL
=======

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

https://bitbucket.org/malb/m4ri

you need to first run the following command:

$ autoreconf --install

Then follow 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

Recent activity

CarloWood

Commits by CarloWood were pushed to CarloWood/M4RI

ff3c379 - Copied the improved code of mzd_col_swap to mzd_col_swap_in_rows and added support for start_row/stop_row. The result has the same speed mzd_col_swap (per row).
CarloWood

Commits by CarloWood were pushed to CarloWood/M4RI

ac49fb8 - Speed up of mzd_col_swap with a factor of two. Plus added a testsuite for it.
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.