Diff for "days24/projects/gf2e"

Differences between revisions 2 and 3

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 Benchmarketing

1000 x 1000 revision 1

n	M4rie mul	Magma mul	M4rie elim	Magma elim
2	0.06	0.02	1.28	0.06
3	0.08	0.05	1.32	0.07
4	0.09	0.11	1.33	0.08
5	0.17	1.79	1.35	0.96
6	0.21	1.83	1.39	0.97
7	0.29	1.84	1.45	1.00
8	0.42	2.50	1.57	1.29
9	4.72	6.44	3.90	2.41
10	11.54	6.43	8.94	2.40

-  ⇤ ← Revision 2 as of 2010-07-18 16:29:58 → 
  Size: 2317
  Editor: MartinAlbrecht
  Comment:
+   ← Revision 3 as of 2010-07-18 16:41:23 → ⇥
  Size: 1525
  Editor: MartinAlbrecht
  Comment:
-Deletions are marked like this.
+Additions are marked like this.
 Line 39:
-{{{
#!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
}}}
+'''1000 x 1000 revision 1'''
||     n || M4rie mul || Magma mul || M4rie elim || Magma elim ||
||     2 ||      0.06 ||      0.02 ||       1.28 ||       0.06 ||
||     3 ||      0.08 ||      0.05 ||       1.32 ||       0.07 ||
||     4 ||      0.09 ||      0.11 ||       1.33 ||       0.08 ||
||     5 ||      0.17 ||      1.79 ||       1.35 ||       0.96 ||
||     6 ||      0.21 ||      1.83 ||       1.39 ||       0.97 ||
||     7 ||      0.29 ||      1.84 ||       1.45 ||       1.00 ||
||     8 ||      0.42 ||      2.50 ||       1.57 ||       1.29 ||
||     9 ||      4.72 ||      6.44 ||       3.90 ||       2.41 ||
||    10 ||     11.54 ||      6.43 ||       8.94 ||       2.40 ||