Processing Math: Done
jsMath
Differences between revisions 17 and 18
⇤ ← Revision 17 as of 2010-07-20 11:59:57 →
Size: 11321
Editor: MartinAlbrecht
Comment:
← Revision 18 as of 2010-07-20 12:02:21 → ⇥
Size: 11426
Editor: MartinAlbrecht
Comment:
Deletions are marked like this. Additions are marked like this.
Line 13: Line 13:

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

Linear algebra over small extensions of GF(2).

Here are some preliminary benchmarks for GF(2^8) from before Sage Days 24:

n

Sage

NTL *2

Magma

M4RIE

1000

49.49

18.84

0.090

0.097

2000

429.05

149.11

0.510

0.529

3000

1494.33

526.57

1.640

2.315

Here is the current multiplication performance compared with Magma:

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

The library is here: http://bitbucket.org/malb/m4rie

Get in contact with Martin Albrecht to get commit rights.

The library needs an updated M4RI which exports more internals for us to use.

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)