Linear algebra over small extensions of GF(2).

People

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

Improve performance of Travolta multiplication

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