|
Size: 10745
Comment:
|
Size: 11209
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 3: | 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 || |
|
| Line 5: | Line 12: |
| * '''Martin Albrecht''' * Ciaran Mullan |
* Martin Albrecht |
| Line 14: | Line 20: |
| == 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 32: | Line 42: |
| === Improve performance of Travolta-Gaussian elimination === * use more than one table |
|
| Line 38: | Line 44: |
| * 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. |
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 |
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 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 |