Diff for "days24/projects/gf2e"

Differences between revisions 1 and 16 (spanning 15 versions)

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:

multiplication_r13.png

People

Martin Albrecht

Library

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.

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

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 Benchmarketing

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 1 as of 2010-07-18 16:00:22 → 
  Size: 781
  Editor: MartinAlbrecht
  Comment:
+   ← Revision 16 as of 2010-07-20 11:59:09 → ⇥
  Size: 11321
  Editor: MartinAlbrecht
  Comment:
-Deletions are marked like this.
+Additions are marked like this.
 Line 3:
+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]]

=== People ===

 * Martin Albrecht
-Line 9:
+Line 24:
-== Sage Patch ==

A patch for Sage is here: https://bitbucket.org/malb/m4rie/downloads/m4rie_for_sage.patch
+The library needs an updated M4RI which exports more internals for us to use.

== 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
-Line 27:
+Line 46:
-=== Improve performance of Travolta-Gaussian elimination ===

 * use more than one table
-Line 33:
+Line 48:
- * get inspiration from M4RM
+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.
-Line 36:
+Line 51:
+== 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 ||

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