Processing Math: Done
jsMath
Differences between revisions 12 and 13
⇤ ← Revision 12 as of 2010-07-18 22:48:30 →
Size: 7903
Editor: MartinAlbrecht
Comment:
← Revision 13 as of 2010-07-19 00:52:26 → ⇥
Size: 9309
Editor: MartinAlbrecht
Comment:
Deletions are marked like this. Additions are marked like this.
Line 171: Line 171:

=== r9 ===

==== 1000 x 1000 ====
|| n || M4rie mul || Magma mul || M4rie elim || Magma elim ||
|| 2 || 0.07 || 0.02 || 0.04 || 0.05 ||
|| 3 || 0.08 || 0.06 || 0.05 || 0.07 ||
|| 4 || 0.11 || 0.11 || 0.05 || 0.09 ||
|| 5 || 0.18 || 1.94 || 0.10 || 1.02 ||
|| 6 || 0.22 || 1.81 || 0.14 || 0.95 ||
|| 7 || 0.29 || 2.00 || 0.20 || 0.99 ||
|| 8 || 0.44 || 2.70 || 0.32 || 1.28 ||
|| 9 || 2.25 || 6.66 || 1.85 || 2.52 ||
|| 10 || 7.35 || 6.40 || 5.34 || 2.40 ||


==== 2000 x 2000 ====
|| n || M4rie mul || Magma mul || M4rie elim || Magma elim ||
|| 2 || 0.38 || 0.16 || 0.20 || 0.24 ||
|| 3 || 0.73 || 0.37 || 0.26 || 0.42 ||
|| 4 || 0.71 || 0.72 || 0.28 || 0.51 ||
|| 5 || 3.08 || 14.40 || 0.68 || 7.28 ||
|| 6 || 4.80 || 15.36 || 0.88 || 7.51 ||
|| 7 || 4.32 || 15.55 || 1.42 || 7.71 ||
|| 8 || 5.77 || 20.25 || 2.35 || 10.69 ||
|| 9 || 19.86 || 52.51 || 10.40 || 19.87 ||
|| 10 || 33.68 || 52.73 || 18.86 || 19.39 ||

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

r5

1000 x 1000

n

M4rie mul

Magma mul

M4rie elim

Magma elim

2

0.07

0.02

0.04

0.04

3

0.08

0.06

0.04

0.09

4

0.11

0.11

0.05

0.09

5

0.18

1.79

0.09

0.95

6

0.23

1.82

0.12

0.97

7

0.30

1.84

0.19

0.98

8

0.44

2.49

0.34

1.31

9

2.22

6.46

1.85

2.39

10

6.52

6.51

5.55

2.39

2000 x 2000

n

M4rie mul

Magma mul

M4rie elim

Magma elim

2

0.38

0.13

0.20

0.17

3

0.54

0.37

0.24

0.36

4

0.60

0.70

0.28

0.47

5

2.65

14.17

0.62

7.26

6

3.44

14.37

0.93

7.39

7

3.39

14.50

1.39

7.46

8

4.72

19.55

2.73

9.92

9

17.09

51.51

10.53

19.14

10

28.51

51.45

21.67

19.10

r9

1000 x 1000

n

M4rie mul

Magma mul

M4rie elim

Magma elim

2

0.07

0.02

0.04

0.05

3

0.08

0.06

0.05

0.07

4

0.11

0.11

0.05

0.09

5

0.18

1.94

0.10

1.02

6

0.22

1.81

0.14

0.95

7

0.29

2.00

0.20

0.99

8

0.44

2.70

0.32

1.28

9

2.25

6.66

1.85

2.52

10

7.35

6.40

5.34

2.40

2000 x 2000

n

M4rie mul

Magma mul

M4rie elim

Magma elim

2

0.38

0.16

0.20

0.24

3

0.73

0.37

0.26

0.42

4

0.71

0.72

0.28

0.51

5

3.08

14.40

0.68

7.28

6

4.80

15.36

0.88

7.51

7

4.32

15.55

1.42

7.71

8

5.77

20.25

2.35

10.69

9

19.86

52.51

10.40

19.87

10

33.68

52.73

18.86

19.39

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