== 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 ||