Matrix Multiplication

Multiplying two random square matrices over \(\mathbb{F}_2\) of the given dimension. Magma and M4RI both implement Strassen-Winograd on top of M4RM (cf. Further Reading). Our multicore code maxes out at 4 cores.

Intel(R) Xeon(R) CPU E5-2667 v2 @ 3.30GHz (strombenzin@rhul)

• M4RI timings were produced as follows:

  $ export OMP_NUM_THREADS=1; for n in 8192 10000 16384 32768 65536; ./bench_multiplication -t 7200 $n $n $n 0 0
  $ export OMP_NUM_THREADS=2; for n in 8192 10000 16384 32768 65536; ./bench_multiplication -t 7200 $n $n $n 0 1
  $ export OMP_NUM_THREADS=4; for n in 8192 10000 16384 32768 65536; ./bench_multiplication -t 7200 $n $n $n 0 1
  

• Magma timings were produced as follows:

  n:=8192; A:=RandomMatrix(GF(2), n, n); B:=RandomMatrix(GF(2), n, n); time C:=A*B;
  

Rank

Computing the rank of random square matrices over \(\mathbb{F}_2\). We are comparing M4RI, Magma and GF2Toolkit. The benchmarks below indicate that we still have some work to do.

Intel(R) Xeon(R) CPU E5-2667 v2 @ 3.30GHz (strombenzin@rhul)

• M4RI timings were produced as follows:

  $ for n in 8192 10000 16384 32768 65536; ./bench_rank -t 7200 $n $n ple 0
  $ for n in 8192 10000 16384 32768 65536; ./bench_rank -t 7200 $n $n m4ri 0
  $ for n in 8192 10000 16384 32768 65536; ./bench_rank -t 7200 $n $n mmpf 0
  

• Magma timings were produced as follows:

  n:=2^16; A:=RandomMatrix(GF(2),n,n); time E:=EchelonForm(A);
  

• GF2Toolkit timings were produced by patching testRankComputation.cc and using the best timing reported (typically for 128-bit wide words).

Old

Timings for previous versions of M4RI are archived here