Differences between revisions 21 and 22
⇤ ← Revision 21 as of 2010-07-20 16:28:01 →
Size: 11910
Editor: MartinAlbrecht
Comment:
← Revision 22 as of 2010-07-20 16:29:23 → ⇥
Size: 11924
Editor: MartinAlbrecht
Comment:
Deletions are marked like this. Additions are marked like this.
Line 41: Line 41:
2. Install this library

First download [[attachment:libm4rie-19780101.0.spkg]]		 2. Download and install [[attachment:libm4rie-19780101.0.spkg]]
Line 51: Line 49:
3. Install the Sage patch 3. Download and apply [[attachment:m4rie_for_sage.patch]]

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_r13.png

Blue means faster than Magma by a factor of eblue. Red means slower than Magma by a factor of ered.

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

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 multiplication

We should try the babsystep giantstep approach from the M4RI library. It will likely be much slower over bigger fields but might be beneficial on smaller fields.

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)