== Linear algebra over small extensions of GF(2) ==
=== Motivation ===
==== Echelon Forms ====
Here are some preliminary benchmarks for row echelon forms of dense random n x n matrices over GF(2^4)
|| n || Sage 4.5 || NTL/2 || Magma 2.15-10 || M4RIE (SD 23.75) || M4RIE (current) ||
|| 1000 || 49.49s || 18.84s || 0.090s || 0.097s || 0.05s ||
|| 2000 || 429.05s || 149.11s || 0.510s || 0.529s || 0.28s ||
|| 3000 || 1494.33s || 526.57s || 1.640s || 2.315s || 1.00s ||
==== Multiplication ====
{{attachment:multiplication_r16.png}}
Blue means faster than Magma by a factor of e^blue^. Red means slower than Magma by a factor of e^-red^.
==== Elimination ====
{{attachment:elimination_r16.png}}
Blue means faster than Magma by a factor of e^blue^. Red means slower than Magma by a factor of e^-red^.
=== People ===
* Martin Albrecht
== Library ==
1. Install an updated M4RI library
{{{
#!sh
wget http://sage.math.washington.edu/home/malb/spkgs/libm4ri-20100701.p1.spkg
tar xvfj libm4ri-20100701.p1.spkg
cd libm4ri-20100701.p1/
rm -rf src
hg clone http://bitbucket.org/malb/m4ri
ln -s m4ri src
cd src
autoreconf --install
cd ..
./spkg-install
}}}
2. Download and install [[attachment:libm4rie-19780101.0.spkg]]
{{{
#!bash
sage -i libm4rie-19780101.0.spkg
}}}
3. Download and apply [[attachment:m4rie_for_sage.patch]]
== Literature ==
* M4RI Elimination http://arxiv.org/abs/1006.1744
* M4RI Multiplication http://arxiv.org/abs/0811.1714
* Bitslice M4RM Multiplication http://arxiv.org/abs/0901.1413
== Todo ==
see http://bitbucket.org/malb/m4rie/issues?status=new&status=open
== History ==
=== r1 ===
==== 1000 x 1000 ====
|| n || M4rie mul || Magma mul || M4rie elim || Magma elim ||
|| 2 || 0.06 || 0.02 || 0.04 || 0.06 ||
|| 3 || 0.08 || 0.06 || 0.05 || 0.10 ||
|| 4 || 0.09 || 0.10 || 0.06 || 0.08 ||
|| 5 || 0.35 || 1.82 || 0.20 || 0.98 ||
|| 6 || 0.44 || 1.82 || 0.22 || 0.97 ||
|| 7 || 0.36 || 1.85 || 0.29 || 0.98 ||
|| 8 || 0.62 || 2.52 || 0.44 || 1.30 ||
|| 9 || 4.94 || 6.46 || 2.93 || 2.41 ||
|| 10 || 11.96 || 6.43 || 8.10 || 2.40 ||
==== 2000 x 2000 ====
|| n || M4rie mul || Magma mul || M4rie elim || Magma elim ||
|| 2 || 0.36 || 0.15 || 0.23 || 0.18 ||
|| 3 || 0.59 || 0.37 || 0.36 || 0.32 ||
|| 4 || 0.59 || 0.69 || 0.41 || 0.47 ||
|| 5 || 2.53 || 14.06 || 1.15 || 7.21 ||
|| 6 || 2.82 || 14.25 || 1.37 || 7.47 ||
|| 7 || 3.43 || 14.41 || 1.63 || 7.42 ||
|| 8 || 4.57 || 19.49 || 2.67 || 9.94 ||
|| 9 || 26.66 || 51.49 || 14.15 || 19.12 ||
|| 10 || 47.09 || 51.48 || 29.82 || 20.02 ||
=== r2 ===
==== 1000 x 1000 ====
|| n || M4rie mul || Magma mul || M4rie elim || Magma elim ||
|| 2 || 0.06 || 0.02 || 0.04 || 0.05 ||
|| 3 || 0.08 || 0.06 || 0.05 || 0.07 ||
|| 4 || 0.08 || 0.11 || 0.06 || 0.08 ||
|| 5 || 0.17 || 1.79 || 0.12 || 0.98 ||
|| 6 || 0.21 || 1.82 || 0.15 || 0.98 ||
|| 7 || 0.29 || 1.85 || 0.23 || 0.98 ||
|| 8 || 0.43 || 2.51 || 0.37 || 1.29 ||
|| 9 || 5.04 || 6.45 || 3.01 || 2.42 ||
|| 10 || 11.95 || 6.45 || 8.11 || 2.39 ||
==== 2000 x 2000 ====
|| n || M4rie mul || Magma mul || M4rie elim || Magma elim ||
|| 2 || 0.36 || 0.15 || 0.24 || 0.17 ||
|| 3 || 0.59 || 0.36 || 0.38 || 0.33 ||
|| 4 || 0.61 || 0.68 || 0.39 || 0.48 ||
|| 5 || 2.55 || 14.02 || 1.27 || 7.20 ||
|| 6 || 3.47 || 14.30 || 1.45 || 7.36 ||
|| 7 || 3.62 || 14.48 || 1.82 || 7.46 ||
|| 8 || 4.80 || 19.67 || 2.77 || 9.95 ||
|| 9 || 27.00 || 51.66 || 14.75 || 19.59 ||
|| 10 || 47.89 || 51.44 || 28.95 || 19.09 ||
=== r3 ===
==== 1000 x 1000 ====
|| n || M4rie mul || Magma mul || M4rie elim || Magma elim ||
|| 2 || 0.06 || 0.02 || 0.04 || 0.08 ||
|| 3 || 0.07 || 0.06 || 0.04 || 0.08 ||
|| 4 || 0.08 || 0.11 || 0.05 || 0.10 ||
|| 5 || 0.17 || 1.79 || 0.09 || 0.95 ||
|| 6 || 0.21 || 1.81 || 0.12 || 0.98 ||
|| 7 || 0.29 || 1.85 || 0.19 || 1.00 ||
|| 8 || 0.43 || 2.51 || 0.33 || 1.29 ||
|| 9 || 4.84 || 6.44 || 2.82 || 2.41 ||
|| 10 || 11.84 || 6.43 || 8.12 || 2.41 ||
==== 2000 x 2000 ====
|| n || M4rie mul || Magma mul || M4rie elim || Magma elim ||
|| 2 || 0.36 || 0.15 || 0.20 || 0.18 ||
|| 3 || 0.58 || 0.36 || 0.23 || 0.34 ||
|| 4 || 0.63 || 0.73 || 0.28 || 0.48 ||
|| 5 || 2.77 || 14.13 || 0.71 || 7.32 ||
|| 6 || 3.18 || 14.31 || 0.90 || 7.46 ||
|| 7 || 4.53 || 14.54 || 1.47 || 7.49 ||
|| 8 || 4.98 || 19.75 || 2.90 || 10.07 ||
|| 9 || 26.83 || 51.71 || 14.86 || 19.23 ||
|| 10 || 48.22 || 51.66 || 32.74 || 19.45 ||
=== r4 ===
==== 1000 x 1000 ====
|| n || M4rie mul || Magma mul || M4rie elim || Magma elim ||
|| 2 || 0.07 || 0.04 || 0.04 || 0.05 ||
|| 3 || 0.09 || 0.06 || 0.04 || 0.09 ||
|| 4 || 0.10 || 0.10 || 0.05 || 0.09 ||
|| 5 || 0.18 || 1.79 || 0.09 || 0.96 ||
|| 6 || 0.21 || 1.83 || 0.13 || 0.97 ||
|| 7 || 0.29 || 1.84 || 0.19 || 0.97 ||
|| 8 || 0.43 || 2.48 || 0.33 || 1.28 ||
|| 9 || 4.62 || 6.42 || 2.78 || 2.39 ||
|| 10 || 11.18 || 6.39 || 7.75 || 2.39 ||
==== 2000 x 2000 ====
|| n || M4rie mul || Magma mul || M4rie elim || Magma elim ||
|| 2 || 0.36 || 0.13 || 0.20 || 0.17 ||
|| 3 || 0.53 || 0.36 || 0.23 || 0.33 ||
|| 4 || 0.63 || 0.75 || 0.28 || 0.47 ||
|| 5 || 3.08 || 14.11 || 0.62 || 7.40 ||
|| 6 || 3.04 || 14.29 || 0.99 || 7.49 ||
|| 7 || 3.62 || 14.45 || 1.35 || 7.46 ||
|| 8 || 4.87 || 19.57 || 2.94 || 9.97 ||
|| 9 || 27.10 || 51.55 || 14.74 || 19.16 ||
|| 10 || 47.95 || 51.45 || 29.59 || 19.18 ||
=== r5 ===
==== 1000 x 1000 ====
|| n || M4rie mul || Magma mul || M4rie elim || Magma elim ||
|| 2 || 0.07 || 0.02 || 0.04 || 0.04 ||
|| 3 || 0.08 || 0.06 || 0.04 || 0.09 ||
|| 4 || 0.11 || 0.11 || 0.05 || 0.09 ||
|| 5 || 0.18 || 1.79 || 0.09 || 0.95 ||
|| 6 || 0.23 || 1.82 || 0.12 || 0.97 ||
|| 7 || 0.30 || 1.84 || 0.19 || 0.98 ||
|| 8 || 0.44 || 2.49 || 0.34 || 1.31 ||
|| 9 || 2.22 || 6.46 || 1.85 || 2.39 ||
|| 10 || 6.52 || 6.51 || 5.55 || 2.39 ||
==== 2000 x 2000 ====
|| n || M4rie mul || Magma mul || M4rie elim || Magma elim ||
|| 2 || 0.38 || 0.13 || 0.20 || 0.17 ||
|| 3 || 0.54 || 0.37 || 0.24 || 0.36 ||
|| 4 || 0.60 || 0.70 || 0.28 || 0.47 ||
|| 5 || 2.65 || 14.17 || 0.62 || 7.26 ||
|| 6 || 3.44 || 14.37 || 0.93 || 7.39 ||
|| 7 || 3.39 || 14.50 || 1.39 || 7.46 ||
|| 8 || 4.72 || 19.55 || 2.73 || 9.92 ||
|| 9 || 17.09 || 51.51 || 10.53 || 19.14 ||
|| 10 || 28.51 || 51.45 || 21.67 || 19.10 ||
=== r9 ===
==== 1000 x 1000 ====
|| n || M4rie mul || Magma mul || M4rie elim || Magma elim ||
|| 2 || 0.07 || 0.02 || 0.04 || 0.05 ||
|| 3 || 0.08 || 0.06 || 0.05 || 0.07 ||
|| 4 || 0.11 || 0.11 || 0.05 || 0.09 ||
|| 5 || 0.18 || 1.94 || 0.10 || 1.02 ||
|| 6 || 0.22 || 1.81 || 0.14 || 0.95 ||
|| 7 || 0.29 || 2.00 || 0.20 || 0.99 ||
|| 8 || 0.44 || 2.70 || 0.32 || 1.28 ||
|| 9 || 2.25 || 6.66 || 1.85 || 2.52 ||
|| 10 || 7.35 || 6.40 || 5.34 || 2.40 ||
==== 2000 x 2000 ====
|| n || M4rie mul || Magma mul || M4rie elim || Magma elim ||
|| 2 || 0.38 || 0.16 || 0.20 || 0.24 ||
|| 3 || 0.73 || 0.37 || 0.26 || 0.42 ||
|| 4 || 0.71 || 0.72 || 0.28 || 0.51 ||
|| 5 || 3.08 || 14.40 || 0.68 || 7.28 ||
|| 6 || 4.80 || 15.36 || 0.88 || 7.51 ||
|| 7 || 4.32 || 15.55 || 1.42 || 7.71 ||
|| 8 || 5.77 || 20.25 || 2.35 || 10.69 ||
|| 9 || 19.86 || 52.51 || 10.40 || 19.87 ||
|| 10 || 33.68 || 52.73 || 18.86 || 19.39 ||
=== r12 ===
We worked on multiplication
==== 1000 x 1000 ====
|| n || M4rie mul || Magma mul || M4rie elim || Magma elim ||
|| 2 || 0.04 || 0.02 || 0.04 || 0.05 ||
|| 3 || 0.04 || 0.05 || 0.08 || 0.06 ||
|| 4 || 0.05 || 0.11 || 0.06 || 0.09 ||
|| 5 || 0.11 || 1.81 || 0.10 || 0.95 ||
|| 6 || 0.14 || 1.83 || 0.14 || 0.97 ||
|| 7 || 0.22 || 1.86 || 0.19 || 0.98 ||
|| 8 || 0.33 || 2.49 || 0.33 || 1.29 ||
|| 9 || 2.34 || 6.43 || 1.87 || 2.40 ||
|| 10 || 6.20 || 6.42 || 5.34 || 2.39 ||
==== 2000 x 2000 ====
|| n || M4rie mul || Magma mul || M4rie elim || Magma elim ||
|| 2 || 0.20 || 0.13 || 0.20 || 0.16 ||
|| 3 || 0.32 || 0.37 || 0.24 || 0.34 ||
|| 4 || 0.35 || 0.67 || 0.29 || 0.48 ||
|| 5 || 1.10 || 14.12 || 0.62 || 7.30 ||
|| 6 || 1.26 || 14.33 || 0.71 || 7.42 ||
|| 7 || 1.67 || 14.49 || 1.07 || 7.50 ||
|| 8 || 3.09 || 19.68 || 2.05 || 10.00 ||
|| 9 || 11.39 || 51.82 || 8.76 || 19.24 ||
|| 10 || 21.93 || 51.74 || 19.39 || 19.31 ||