days24/projects/gf2e - Sagemath Wiki

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

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

Elimination

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

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

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

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