malb / M4RI (http://m4ri.sagemath.org/)

M4RI is a library for fast arithmetic with dense matrices over F2. It was started by Gregory Bard, is maintained by Martin Albrecht. Several people contributed to it. 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+).

Clone this repository (size: 730.5 KB): HTTPS / SSH
$ hg clone http://bitbucket.org/malb/m4ri/
commit 314: a2a70d533ae6
parent 313: 39b9a8b9767e
renamed mzd_apply_p_right_tri to mzd_apply_p_right_trans_tri because this is what it does some some sparse-ish performance enhancements defaulttip
Martin Albrecht / malb
3 months ago
View at rev
M4RI /
filename size last modified message
m4  
src  
testsuite  
.hgtags 348 B 3 months ago Added tag release-20091101 for changeset 66644740d92d
AUTHORS 1.1 KB 10 months ago added Macro as an author
COPYING 17.6 KB 14 months ago added COPYING file to repository because autotools insist…
ChangeLog 0 B 20 months ago checking in all files that automake doesn't autogenerate
Makefile.am 1.3 KB 3 months ago considerable protability improvement in configure.ac due to…
NEWS 0 B 20 months ago checking in all files that automake doesn't autogenerate
README 1.9 KB 8 months ago experiments with OpenMP
configure.ac 1.6 KB 3 months ago considerable protability improvement in configure.ac due to…
ltmain.sh 237.7 KB 9 months ago added test code for mzd_kernel_left_pluq()
m4ri 4 B 15 months ago improved testsuite build process
m4ri.sln 878 B 21 months ago added support for Visual Studio 2008 Express
m4ri.vcproj 5.1 KB 13 months ago updated MSVC project to include pluq_mmpf and solve

README

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

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 parallisation 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 avised
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.