Opened 9 years ago
Last modified 4 years ago
#12103 closed defect
Use MeatAxe as an optional back end for dense matrices over `GF(p^n)`, p odd, n>1, `p^n<255` — at Version 3
Reported by: | SimonKing | Owned by: | jason, was |
---|---|---|---|
Priority: | major | Milestone: | sage-7.0 |
Component: | packages: optional | Keywords: | linear algebra, MeatAxe |
Cc: | malb, jdemeyer, vbraun | Merged in: | |
Authors: | Simon King | Reviewers: | |
Report Upstream: | Reported upstream. No feedback yet. | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #9562 #4260 | Stopgaps: |
Description (last modified by )
Sage has (or will soon have) fairly good implementations of dense matrices over GF(2)
, over GF(2^e)
(#9562) and over GF(p)
(p prime, #4260). However, it uses generic code for dense matrices over GF(p^n)
, p odd, n>1, p^n<255
.
I suggest to use a major modification of MeatAxe Release 2.2.4
instead of the basic implementation. More on the modifications and the reason for choosing an old release is explained in the comments.
This is awfully slow:
sage: MS = MatrixSpace(GF(5^3,'y'),2000) sage: %time A = MS.random_element() CPU times: user 6.36 s, sys: 0.02 s, total: 6.39 s Wall time: 6.41 s sage: type(A) <type 'sage.matrix.matrix_generic_dense.Matrix_generic_dense'> sage: B = MS.random_element() sage: %time A*B # using 6.3% of my computer's memory CPU times: user 744.20 s, sys: 1.18 s, total: 745.38 s Wall time: 747.69 s 2000 x 2000 dense matrix over Finite Field in y of size 5^3 sage: %time ~A # using 10.4% of my computer's memory CPU times: user 1096.74 s, sys: 1.30 s, total: 1098.05 s Wall time: 1101.24 s 2000 x 2000 dense matrix over Finite Field in y of size 5^3 sage: %time A.echelon_form() # using 10.4% of my computer's memory CPU times: user 378.62 s, sys: 0.33 s, total: 378.95 s Wall time: 380.06 s 2000 x 2000 dense matrix over Finite Field in y of size 5^3
With the optional spkg and the patch, one gets a clear improvement.
sage: MS = MatrixSpace(GF(5^3,'y'),2000) sage: %time A = MS.random_element() CPU times: user 0.32 s, sys: 0.00 s, total: 0.32 s Wall time: 0.33 s sage: type(A) <type 'sage.matrix.matrix_modpn_dense.Matrix_modpn_dense'> sage: B = MS.random_element() # The following uses Strassen-Winograd multiplication sage: %time A*B # using 3.5% of my computer's memory CPU times: user 7.68 s, sys: 0.01 s, total: 7.69 s Wall time: 7.72 s 2000 x 2000 dense matrix over Finite Field in y of size 5^3 # The following is school book multiplication; # that's more or less the original meataxe speed: sage: %time A._multiply_classical(B) # using 3.6% of my computer's memory CPU times: user 11.68 s, sys: 0.02 s, total: 11.70 s Wall time: 11.73 s 2000 x 2000 dense matrix over Finite Field in y of size 5^3 # Strassen is not implemented for inversion and echelon form. sage: %time ~A # using 3.8% of my computer's memory CPU times: user 23.55 s, sys: 0.00 s, total: 23.55 s Wall time: 23.62 s 2000 x 2000 dense matrix over Finite Field in y of size 5^3 sage: %time A.echelon_form() #using 3.9% of my computer's memory CPU times: user 11.73 s, sys: 0.01 s, total: 11.74 s Wall time: 11.78 s 2000 x 2000 dense matrix over Finite Field in y of size 5^3
I think the component is "linear algebra", even though it is about an optional package.
How to install stuff
- Apply the dependencies
- Install the optional libmeataxe spkg
- Apply either trac12103_meataxe.patch or trac12103_meataxe_rel11900.patch, depending on whether or not you have #11900 applied.
- Apply trac12103_meataxe_docfix.patch
Change History (6)
comment:1 Changed 9 years ago by
- Description modified (diff)
- Status changed from new to needs_review
Changed 9 years ago by
Use MeatAxe
as back end for linear algebra over some finite fields. Relative to #11900
comment:2 Changed 9 years ago by
I have updated both patches, because I wanted to add one method: matrix_from_rows
. One could rely on the generic implementation, but in some application I need this to be fast:
sage: MS = MatrixSpace(GF(5^3,'y'),3,2) sage: A = MS(range(6)) sage: A [0 1] [2 3] [4 0] sage: A.matrix_from_rows([2,1]) [4 0] [2 3] sage: A.matrix_from_rows([1,1]) [2 3] [2 3]
comment:3 Changed 8 years ago by
- Description modified (diff)
Apparently there has been a name change MatrixSpace_generic
to MatrixSpace
. The result is one doctest failure in my original patch. I am not sure where that name change happened (perhaps it is in one of my patches that aren't in vanilla Sage yet). Therefore I added a second patch, that may or may not be necessary.
Apply trac12103_meataxe_rel11900.patch trac12103_meataxe_docfix.patch
Here is more on
libmeataxe-1.0.spkg
.I started with Release 2.2.4 of the Aachen
C MeatAxe
. This is partially because I first came in touch withMeatAxe
by old code of David Green, who was using the 2.2.3 release.MeatAxe 2.2.4
was released under GPL2+, which should be fine. There are more recent releases. However, according to Michael Ringe, while the interface changed substantially, the linear algebra is more or less the same.The spkg contains the unmodified sources in the folder
src/
, which is not under version control. The filepatches/libmeataxe.patch
provides my modification. Of course, if one installs the package, the patch will automatically be applied. Here is a summary of my changes:MeatAxe
provides some executables that operate on matrices stored in files. I strip it down, such that the executables are not built and only a C library remains (this is libmeataxe-1.0.spkg). I wrap the C library using Cython (this is trac12103_meataxe.patch)MeatAxe
uses school book multiplication. I added Strassen-Winograd multiplication, using a schedule that minimizes memory consumption. Seesrc/src/window.c
.MTXLIB
was supposed to tellMeatAxe
where to find multiplication tables. However, this never worked for me. I fix it, so that now multiplication tables in$SAGE_ROOT/local
are used, that are created when the package is installed.T_STRING
intoT_STRINGS
,MTXmatid
.The aim of this ticket is to make the modified
MeatAxe
an optional back end for dense matrices overGF(p^n)
, p>2 prime, n>1,p^n<255
. Currently, one needs to install an spkg and a patch to the Sage library.I would prefer to have it all in one, such that
sage -i libmeataxe-1.0.spkg
would automatically patch the Sage library. Question to Sage experts: Is that possible?Anyway, I think it can be reviewed...