Differences between revisions 1 and 27 (spanning 26 versions)
⇤ ← Revision 1 as of 2010-07-18 16:00:22 →
Size: 781
Editor: MartinAlbrecht
Comment:
← Revision 27 as of 2010-07-21 09:49:48 → ⇥
Size: 11632
Editor: MartinAlbrecht
Comment:
Deletions are marked like this. Additions are marked like this.
Line 1: Line 1:
Linear algebra over small extensions of GF(2). == Linear algebra over small extensions of GF(2) ==

=== Motivation ===

==== Echelon Forms ====
Here are some preliminary benchmarks for row echelon forms of dense random n x n matrices over GF(2^4)

|| n || Sage 4.5 || NTL/2 || Magma 2.15-10 || M4RIE (SD 23.75) || M4RIE (current) ||
|| 1000 || 49.49s || 18.84s || 0.090s || 0.097s || 0.05s ||
|| 2000 || 429.05s || 149.11s || 0.510s || 0.529s || 0.28s ||
|| 3000 || 1494.33s || 526.57s || 1.640s || 2.315s || 1.00s ||

==== Multiplication ====

{{attachment:multiplication_r16.png}}

Blue means faster than Magma by a factor of e^blue^. Red means slower than Magma by a factor of e^-red^.

==== Elimination ====

{{attachment:elimination_r16.png}}

Blue means faster than Magma by a factor of e^blue^. Red means slower than Magma by a factor of e^-red^.


=== People ===

 * Martin Albrecht
Line 5: Line 32:
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		 1. Install an updated M4RI library

{{{
#!sh
wget http://sage.math.washington.edu/home/malb/spkgs/libm4ri-20100701.p1.spkg
tar xvfj libm4ri-20100701.p1.spkg
cd libm4ri-20100701.p1/
rm -rf src
hg clone http://bitbucket.org/malb/m4ri
ln -s m4ri src
cd src
autoreconf --install
cd ..
./spkg-install
}}}

2. Download and install [[attachment:libm4rie-19780101.0.spkg]]

{{{
#!bash
sage -i libm4rie-19780101.0.spkg
}}}
 

3. Download and apply [[attachment:m4rie_for_sage.patch]]

== Literature ==

 * M4RI Elimination http://arxiv.org/abs/1006.1744
 * M4RI Multiplication http://arxiv.org/abs/0811.1714
 * Bitslice M4RM Multiplication http://arxiv.org/abs/0901.1413
Line 15: Line 66:
=== 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 ===		 see http://bitbucket.org/malb/m4rie/issues?status=new&status=open

== History ==

=== 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 ||

Linear algebra over small extensions of GF(2)

Motivation

Echelon Forms

Here are some preliminary benchmarks for row echelon forms of dense random n x n matrices over GF(2^4)

n

Sage 4.5

NTL/2

Magma 2.15-10

M4RIE (SD 23.75)

M4RIE (current)

1000

49.49s

18.84s

0.090s

0.097s

0.05s

2000

429.05s

149.11s

0.510s

0.529s

0.28s

3000

1494.33s

526.57s

1.640s

2.315s

1.00s

Multiplication

multiplication_r16.png

Blue means faster than Magma by a factor of eblue. Red means slower than Magma by a factor of e-red.

Elimination

elimination_r16.png

Blue means faster than Magma by a factor of eblue. Red means slower than Magma by a factor of e-red.

People

  • Martin Albrecht

Library

1. Install an updated M4RI library 

wget http://sage.math.washington.edu/home/malb/spkgs/libm4ri-20100701.p1.spkg
tar xvfj libm4ri-20100701.p1.spkg
cd libm4ri-20100701.p1/
rm -rf src
hg clone http://bitbucket.org/malb/m4ri
ln -s m4ri src
cd src
autoreconf --install
cd ..
./spkg-install

2. Download and install libm4rie-19780101.0.spkg 

sage -i libm4rie-19780101.0.spkg

3. Download and apply m4rie_for_sage.patch

Literature

Todo

see http://bitbucket.org/malb/m4rie/issues?status=new&status=open

History

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)