Diff for "days24/projects/gf2e"

Differences between revisions 18 and 27 (spanning 9 versions)

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

-  ⇤ ← Revision 18 as of 2010-07-20 12:02:21 → 
  Size: 11426
  Editor: MartinAlbrecht
  Comment:
+   ← Revision 27 as of 2010-07-21 09:49:48 → ⇥
  Size: 11632
  Editor: MartinAlbrecht
  Comment:
-Deletions are marked like this.
+Additions are marked like this.
 Line 1:
-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:

{{attachment:multiplication_r13.png}}

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) ==

=== 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 ====

{{attachment:multiplication_r16.png}}

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

==== Elimination ====

{{attachment:elimination_r16.png}}

Blue means faster than Magma by a factor of e^blue^. Red means slower than Magma by a factor of e^-red^.
-Line 22:
+Line 32:
-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.
+. Install an updated M4RI library

{{{
#!sh
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 [[attachment:libm4rie-19780101.0.spkg]]

{{{
#!bash
sage -i libm4rie-19780101.0.spkg
}}}
 

3. Download and apply [[attachment:m4rie_for_sage.patch]]
-Line 36:
+Line 66:
-=== 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 ==
+see http://bitbucket.org/malb/m4rie/issues?status=new&status=open

== History ==