Diff for "days24/projects/gf2e"

Differences between revisions 23 and 24

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.

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

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

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

-  ⇤ ← Revision 23 as of 2010-07-20 16:30:10 → 
  Size: 11657
  Editor: MartinAlbrecht
  Comment:
+   ← Revision 24 as of 2010-07-20 21:21:52 → ⇥
  Size: 11657
  Editor: MartinAlbrecht
  Comment:
-Deletions are marked like this.
+Additions are marked like this.
 Line 15:
-{{attachment:multiplication_r13.png}}
+{{attachment:multiplication_r16.png}}