Differences between revisions 2 and 3
Revision 2 as of 2010-07-18 16:29:58
Size: 2317
Comment:
Revision 3 as of 2010-07-18 16:41:23
Size: 1525
Comment:
Deletions are marked like this. Additions are marked like this.
Line 39: 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 ||

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

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

days24/projects/gf2e (last edited 2010-07-21 09:49:48 by MartinAlbrecht)