|
⇤ ← Revision 1 as of 2010-07-18 16:00:22
Size: 781
Comment:
|
Size: 2317
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 36: | Line 36: |
== Preliminary Bench***market***ing == {{{ #!python sage: m,n = 3000, 3000 sage: for i in range(2,10+1): ... K.<a> = GF(2^i) ... A = random_matrix(K, m, n) ... t = cputime() ... A.echelonize('travolta') ... print "%2d: %5.2f"%(i, cputime(t)) 2: 0.76 3: 2.59 4: 2.45 5: 7.98 6: 8.39 7: 9.22 8: 11.58 9: 41.59 10: 71.06 }}} {{{ #!python sage: %magma sage: for i in [2..10] do ... K<a> := GF(2^i); ... A := RandomMatrix(K,3000,3000); ... t := Cputime(); ... E:= EchelonForm(A); ... print i, Cputime(t); ... sage: end for 2 0.710 3 0.910 4 1.630 5 24.830 6 26.110 7 26.270 8 36.390 9 68.090 10 66.800 }}} {{{ #!python sage: m,n = 3000, 3000 sage: for i in range(2,10+1): ... K.<a> = GF(2^i) ... A = random_matrix(K, m, n) ... B = random_matrix(K, m, n) ... t = cputime() ... C = A*B ... print "%2d: %5.2f"%(i, cputime(t)) 2: 2.10 3: 6.35 4: 6.18 5: 18.75 6: 19.89 7: 22.15 8: 25.87 9: 113.10 10: 153.06 }}} {{{ #!python sage: m,n = 3000,3000 sage: for i in range(2,10+1): ... _ = magma.eval("K<a> := GF(2^%d)"%i) ... A = magma("RandomMatrix(K,%d,%d)"%(3000,3000)) ... B = magma("RandomMatrix(K,%d,%d)"%(3000,3000)) ... t = magma.cputime() ... C = A*B ... print "%2d: %5.2f"%(i, magma.cputime(t)) 2: 0.44 3: 1.19 4: 3.85 5: 62.17 6: 61.62 7: 73.85 8: 137.72 9: 274.83 10: 312.15 }}} |
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
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
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
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
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