Diff for "days24/projects/gf2e"

Differences between revisions 25 and 26

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

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 25 as of 2010-07-20 21:44:41 → 
  Size: 11834
  Editor: MartinAlbrecht
  Comment:
+   ← Revision 26 as of 2010-07-21 08:13:00 → ⇥
  Size: 11831
  Editor: MartinAlbrecht
  Comment:
-Deletions are marked like this.
+Additions are marked like this.
 Line 19:
-==== Multiplication ====
+==== Elimination ====