Linear algebra over small extensions of GF(2).
Library
The library is here: http://bitbucket.org/malb/m4rie
Get in contact with Martin Albrecht to get commit rights.
Sage Patch
A patch for Sage is here: https://bitbucket.org/malb/m4rie/downloads/m4rie_for_sage.patch
Todo
Implement simple functions in m4rie
Examples: stacking, augmenting, printing
Write C test code
Write C documentation
Implement methods of Sage class
Write documentation for Sage class
Improve performance of Travolta-Gaussian elimination
- use more than one table
Improve performance of Travolta multiplication
- get inspiration from M4RM
Implement Strassen multiplication
Preliminary Bench***market***ing
Toggle line numbers
1 sage: m,n = 3000, 3000
2 sage: for i in range(2,10+1):
3 ... K.<a> = GF(2^i)
4 ... A = random_matrix(K, m, n)
5 ... t = cputime()
6 ... A.echelonize('travolta')
7 ... print "%2d: %5.2f"%(i, cputime(t))
8 2: 0.76
9 3: 2.59
10 4: 2.45
11 5: 7.98
12 6: 8.39
13 7: 9.22
14 8: 11.58
15 9: 41.59
16 10: 71.06
Toggle line numbers
1 sage: %magma
2 sage: for i in [2..10] do
3 ... K<a> := GF(2^i);
4 ... A := RandomMatrix(K,3000,3000);
5 ... t := Cputime();
6 ... E:= EchelonForm(A);
7 ... print i, Cputime(t);
8 ...
9 sage: end for
10 2 0.710
11 3 0.910
12 4 1.630
13 5 24.830
14 6 26.110
15 7 26.270
16 8 36.390
17 9 68.090
18 10 66.800
Toggle line numbers
1 sage: m,n = 3000, 3000
2 sage: for i in range(2,10+1):
3 ... K.<a> = GF(2^i)
4 ... A = random_matrix(K, m, n)
5 ... B = random_matrix(K, m, n)
6 ... t = cputime()
7 ... C = A*B
8 ... print "%2d: %5.2f"%(i, cputime(t))
9 2: 2.10
10 3: 6.35
11 4: 6.18
12 5: 18.75
13 6: 19.89
14 7: 22.15
15 8: 25.87
16 9: 113.10
17 10: 153.06
Toggle line numbers
1 sage: m,n = 3000,3000
2 sage: for i in range(2,10+1):
3 ... _ = magma.eval("K<a> := GF(2^%d)"%i)
4 ... A = magma("RandomMatrix(K,%d,%d)"%(3000,3000))
5 ... B = magma("RandomMatrix(K,%d,%d)"%(3000,3000))
6 ... t = magma.cputime()
7 ... C = A*B
8 ... print "%2d: %5.2f"%(i, magma.cputime(t))
9 2: 0.44
10 3: 1.19
11 4: 3.85
12 5: 62.17
13 6: 61.62
14 7: 73.85
15 8: 137.72
16 9: 274.83
17 10: 312.15