Processing Math: Done
jsMath
Differences between revisions 1 and 11 (spanning 10 versions)
⇤ ← Revision 1 as of 2010-07-18 16:00:22 →
Size: 781
Editor: MartinAlbrecht
Comment:
← Revision 11 as of 2010-07-18 22:20:32 → ⇥
Size: 6501
Editor: MartinAlbrecht
Comment:
Deletions are marked like this. Additions are marked like this.
Line 2: Line 2:

=== People ===

 * '''Martin Albrecht'''
 * Ciaran Mullan
Line 36: Line 41:

== Preliminary Bench***market***ing ==

=== r1 ===
==== 1000 x 1000 ====
|| n || M4rie mul || Magma mul || M4rie elim || Magma elim ||
|| 2 || 0.06 || 0.02 || 0.04 || 0.06 ||
|| 3 || 0.08 || 0.06 || 0.05 || 0.10 ||
|| 4 || 0.09 || 0.10 || 0.06 || 0.08 ||
|| 5 || 0.35 || 1.82 || 0.20 || 0.98 ||
|| 6 || 0.44 || 1.82 || 0.22 || 0.97 ||
|| 7 || 0.36 || 1.85 || 0.29 || 0.98 ||
|| 8 || 0.62 || 2.52 || 0.44 || 1.30 ||
|| 9 || 4.94 || 6.46 || 2.93 || 2.41 ||
|| 10 || 11.96 || 6.43 || 8.10 || 2.40 ||

==== 2000 x 2000 ====
|| n || M4rie mul || Magma mul || M4rie elim || Magma elim ||
|| 2 || 0.36 || 0.15 || 0.23 || 0.18 ||
|| 3 || 0.59 || 0.37 || 0.36 || 0.32 ||
|| 4 || 0.59 || 0.69 || 0.41 || 0.47 ||
|| 5 || 2.53 || 14.06 || 1.15 || 7.21 ||
|| 6 || 2.82 || 14.25 || 1.37 || 7.47 ||
|| 7 || 3.43 || 14.41 || 1.63 || 7.42 ||
|| 8 || 4.57 || 19.49 || 2.67 || 9.94 ||
|| 9 || 26.66 || 51.49 || 14.15 || 19.12 ||
|| 10 || 47.09 || 51.48 || 29.82 || 20.02 ||


=== r2 ===
==== 1000 x 1000 ====
|| n || M4rie mul || Magma mul || M4rie elim || Magma elim ||
|| 2 || 0.06 || 0.02 || 0.04 || 0.05 ||
|| 3 || 0.08 || 0.06 || 0.05 || 0.07 ||
|| 4 || 0.08 || 0.11 || 0.06 || 0.08 ||
|| 5 || 0.17 || 1.79 || 0.12 || 0.98 ||
|| 6 || 0.21 || 1.82 || 0.15 || 0.98 ||
|| 7 || 0.29 || 1.85 || 0.23 || 0.98 ||
|| 8 || 0.43 || 2.51 || 0.37 || 1.29 ||
|| 9 || 5.04 || 6.45 || 3.01 || 2.42 ||
|| 10 || 11.95 || 6.45 || 8.11 || 2.39 ||

==== 2000 x 2000 ====
|| n || M4rie mul || Magma mul || M4rie elim || Magma elim ||
|| 2 || 0.36 || 0.15 || 0.24 || 0.17 ||
|| 3 || 0.59 || 0.36 || 0.38 || 0.33 ||
|| 4 || 0.61 || 0.68 || 0.39 || 0.48 ||
|| 5 || 2.55 || 14.02 || 1.27 || 7.20 ||
|| 6 || 3.47 || 14.30 || 1.45 || 7.36 ||
|| 7 || 3.62 || 14.48 || 1.82 || 7.46 ||
|| 8 || 4.80 || 19.67 || 2.77 || 9.95 ||
|| 9 || 27.00 || 51.66 || 14.75 || 19.59 ||
|| 10 || 47.89 || 51.44 || 28.95 || 19.09 ||


=== r3 ===
==== 1000 x 1000 ====
|| n || M4rie mul || Magma mul || M4rie elim || Magma elim ||
|| 2 || 0.06 || 0.02 || 0.04 || 0.08 ||
|| 3 || 0.07 || 0.06 || 0.04 || 0.08 ||
|| 4 || 0.08 || 0.11 || 0.05 || 0.10 ||
|| 5 || 0.17 || 1.79 || 0.09 || 0.95 ||
|| 6 || 0.21 || 1.81 || 0.12 || 0.98 ||
|| 7 || 0.29 || 1.85 || 0.19 || 1.00 ||
|| 8 || 0.43 || 2.51 || 0.33 || 1.29 ||
|| 9 || 4.84 || 6.44 || 2.82 || 2.41 ||
|| 10 || 11.84 || 6.43 || 8.12 || 2.41 ||

==== 2000 x 2000 ====
|| n || M4rie mul || Magma mul || M4rie elim || Magma elim ||
|| 2 || 0.36 || 0.15 || 0.20 || 0.18 ||
|| 3 || 0.58 || 0.36 || 0.23 || 0.34 ||
|| 4 || 0.63 || 0.73 || 0.28 || 0.48 ||
|| 5 || 2.77 || 14.13 || 0.71 || 7.32 ||
|| 6 || 3.18 || 14.31 || 0.90 || 7.46 ||
|| 7 || 4.53 || 14.54 || 1.47 || 7.49 ||
|| 8 || 4.98 || 19.75 || 2.90 || 10.07 ||
|| 9 || 26.83 || 51.71 || 14.86 || 19.23 ||
|| 10 || 48.22 || 51.66 || 32.74 || 19.45 ||

=== r4 ===
==== 1000 x 1000 ====
|| n || M4rie mul || Magma mul || M4rie elim || Magma elim ||
|| 2 || 0.07 || 0.04 || 0.04 || 0.05 ||
|| 3 || 0.09 || 0.06 || 0.04 || 0.09 ||
|| 4 || 0.10 || 0.10 || 0.05 || 0.09 ||
|| 5 || 0.18 || 1.79 || 0.09 || 0.96 ||
|| 6 || 0.21 || 1.83 || 0.13 || 0.97 ||
|| 7 || 0.29 || 1.84 || 0.19 || 0.97 ||
|| 8 || 0.43 || 2.48 || 0.33 || 1.28 ||
|| 9 || 4.62 || 6.42 || 2.78 || 2.39 ||
|| 10 || 11.18 || 6.39 || 7.75 || 2.39 ||

==== 2000 x 2000 ====

|| n || M4rie mul || Magma mul || M4rie elim || Magma elim ||
|| 2 || 0.36 || 0.13 || 0.20 || 0.17 ||
|| 3 || 0.53 || 0.36 || 0.23 || 0.33 ||
|| 4 || 0.63 || 0.75 || 0.28 || 0.47 ||
|| 5 || 3.08 || 14.11 || 0.62 || 7.40 ||
|| 6 || 3.04 || 14.29 || 0.99 || 7.49 ||
|| 7 || 3.62 || 14.45 || 1.35 || 7.46 ||
|| 8 || 4.87 || 19.57 || 2.94 || 9.97 ||
|| 9 || 27.10 || 51.55 || 14.74 || 19.16 ||
|| 10 || 47.95 || 51.45 || 29.59 || 19.18 ||

Linear algebra over small extensions of GF(2).

People

  • Martin Albrecht

  • Ciaran Mullan

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

r1

1000 x 1000

n

M4rie mul

Magma mul

M4rie elim

Magma elim

2

0.06

0.02

0.04

0.06

3

0.08

0.06

0.05

0.10

4

0.09

0.10

0.06

0.08

5

0.35

1.82

0.20

0.98

6

0.44

1.82

0.22

0.97

7

0.36

1.85

0.29

0.98

8

0.62

2.52

0.44

1.30

9

4.94

6.46

2.93

2.41

10

11.96

6.43

8.10

2.40

2000 x 2000

n

M4rie mul

Magma mul

M4rie elim

Magma elim

2

0.36

0.15

0.23

0.18

3

0.59

0.37

0.36

0.32

4

0.59

0.69

0.41

0.47

5

2.53

14.06

1.15

7.21

6

2.82

14.25

1.37

7.47

7

3.43

14.41

1.63

7.42

8

4.57

19.49

2.67

9.94

9

26.66

51.49

14.15

19.12

10

47.09

51.48

29.82

20.02

r2

1000 x 1000

n

M4rie mul

Magma mul

M4rie elim

Magma elim

2

0.06

0.02

0.04

0.05

3

0.08

0.06

0.05

0.07

4

0.08

0.11

0.06

0.08

5

0.17

1.79

0.12

0.98

6

0.21

1.82

0.15

0.98

7

0.29

1.85

0.23

0.98

8

0.43

2.51

0.37

1.29

9

5.04

6.45

3.01

2.42

10

11.95

6.45

8.11

2.39

2000 x 2000

n

M4rie mul

Magma mul

M4rie elim

Magma elim

2

0.36

0.15

0.24

0.17

3

0.59

0.36

0.38

0.33

4

0.61

0.68

0.39

0.48

5

2.55

14.02

1.27

7.20

6

3.47

14.30

1.45

7.36

7

3.62

14.48

1.82

7.46

8

4.80

19.67

2.77

9.95

9

27.00

51.66

14.75

19.59

10

47.89

51.44

28.95

19.09

r3

1000 x 1000

n

M4rie mul

Magma mul

M4rie elim

Magma elim

2

0.06

0.02

0.04

0.08

3

0.07

0.06

0.04

0.08

4

0.08

0.11

0.05

0.10

5

0.17

1.79

0.09

0.95

6

0.21

1.81

0.12

0.98

7

0.29

1.85

0.19

1.00

8

0.43

2.51

0.33

1.29

9

4.84

6.44

2.82

2.41

10

11.84

6.43

8.12

2.41

2000 x 2000

n

M4rie mul

Magma mul

M4rie elim

Magma elim

2

0.36

0.15

0.20

0.18

3

0.58

0.36

0.23

0.34

4

0.63

0.73

0.28

0.48

5

2.77

14.13

0.71

7.32

6

3.18

14.31

0.90

7.46

7

4.53

14.54

1.47

7.49

8

4.98

19.75

2.90

10.07

9

26.83

51.71

14.86

19.23

10

48.22

51.66

32.74

19.45

r4

1000 x 1000

n

M4rie mul

Magma mul

M4rie elim

Magma elim

2

0.07

0.04

0.04

0.05

3

0.09

0.06

0.04

0.09

4

0.10

0.10

0.05

0.09

5

0.18

1.79

0.09

0.96

6

0.21

1.83

0.13

0.97

7

0.29

1.84

0.19

0.97

8

0.43

2.48

0.33

1.28

9

4.62

6.42

2.78

2.39

10

11.18

6.39

7.75

2.39

2000 x 2000

n

M4rie mul

Magma mul

M4rie elim

Magma elim

2

0.36

0.13

0.20

0.17

3

0.53

0.36

0.23

0.33

4

0.63

0.75

0.28

0.47

5

3.08

14.11

0.62

7.40

6

3.04

14.29

0.99

7.49

7

3.62

14.45

1.35

7.46

8

4.87

19.57

2.94

9.97

9

27.10

51.55

14.74

19.16

10

47.95

51.45

29.59

19.18

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