Processing Math: Done
No jsMath TeX fonts found -- using unicode fonts instead.
This may be slow and might not print well.
Use the jsMath control panel to get additional information.
jsMath Control PanelHide this Message

jsMath
Differences between revisions 13 and 14
⇤ ← Revision 13 as of 2010-07-19 00:52:26 →
Size: 9309
Editor: MartinAlbrecht
Comment:
← Revision 14 as of 2010-07-19 17:11:05 → ⇥
Size: 10745
Editor: MartinAlbrecht
Comment:
Deletions are marked like this. Additions are marked like this.
Line 198: Line 198:

=== r12 ===

We worked on multiplication

==== 1000 x 1000 ====
|| n || M4rie mul || Magma mul || M4rie elim || Magma elim ||
|| 2 || 0.04 || 0.02 || 0.04 || 0.05 ||
|| 3 || 0.04 || 0.05 || 0.08 || 0.06 ||
|| 4 || 0.05 || 0.11 || 0.06 || 0.09 ||
|| 5 || 0.11 || 1.81 || 0.10 || 0.95 ||
|| 6 || 0.14 || 1.83 || 0.14 || 0.97 ||
|| 7 || 0.22 || 1.86 || 0.19 || 0.98 ||
|| 8 || 0.33 || 2.49 || 0.33 || 1.29 ||
|| 9 || 2.34 || 6.43 || 1.87 || 2.40 ||
|| 10 || 6.20 || 6.42 || 5.34 || 2.39 ||

==== 2000 x 2000 ====
|| n || M4rie mul || Magma mul || M4rie elim || Magma elim ||
|| 2 || 0.20 || 0.13 || 0.20 || 0.16 ||
|| 3 || 0.32 || 0.37 || 0.24 || 0.34 ||
|| 4 || 0.35 || 0.67 || 0.29 || 0.48 ||
|| 5 || 1.10 || 14.12 || 0.62 || 7.30 ||
|| 6 || 1.26 || 14.33 || 0.71 || 7.42 ||
|| 7 || 1.67 || 14.49 || 1.07 || 7.50 ||
|| 8 || 3.09 || 19.68 || 2.05 || 10.00 ||
|| 9 || 11.39 || 51.82 || 8.76 || 19.24 ||
|| 10 || 21.93 || 51.74 || 19.39 || 19.31 ||

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

r12

We worked on multiplication

1000 x 1000

n

M4rie mul

Magma mul

M4rie elim

Magma elim

2

0.04

0.02

0.04

0.05

3

0.04

0.05

0.08

0.06

4

0.05

0.11

0.06

0.09

5

0.11

1.81

0.10

0.95

6

0.14

1.83

0.14

0.97

7

0.22

1.86

0.19

0.98

8

0.33

2.49

0.33

1.29

9

2.34

6.43

1.87

2.40

10

6.20

6.42

5.34

2.39

2000 x 2000

n

M4rie mul

Magma mul

M4rie elim

Magma elim

2

0.20

0.13

0.20

0.16

3

0.32

0.37

0.24

0.34

4

0.35

0.67

0.29

0.48

5

1.10

14.12

0.62

7.30

6

1.26

14.33

0.71

7.42

7

1.67

14.49

1.07

7.50

8

3.09

19.68

2.05

10.00

9

11.39

51.82

8.76

19.24

10

21.93

51.74

19.39

19.31

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