Opened 9 years ago
Last modified 5 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 46
Reported by:  SimonKing  Owned by:  jason, was 

Priority:  major  Milestone:  sage7.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:  u/SimonKing/meataxe (Commits, GitHub, GitLab)  Commit:  d9675fbca6cf8647548f6f37522d2c388812669d 
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
.
The original suggestion was to use a major modification of MeatAxe Release 2.2.4
instead of the basic implementation. The timings below are with that old version (it is identical with 2.2.3 except for the GPL licence, and 2.2.3 was before 1998).
I now suggest to try and do the same with the latest MeatAxe release 2.4.24, which is from 2011. There also is an experimental 2.5.0 from 2003, but I think we shouldn't rely on that.
Sources
http://www.math.rwthaachen.de/~MTX/meataxe2.4.24.tar.gz
What is done
There is no spkgcheck. However, if SAGE_CHECK=yes or of one does sage i c meataxe
, then a test suite is executed as part of building the package.
It is my experience that the tests pass most of the time. I can not explain why sometimes they don't.
What is missing
Currently, the spkg installs libmtx.a and installs some binaries. However, I also intend to add a Cython wrapper so that one can use MeatAxe matrices in Sage.
Here is the original ticket description:
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 StrassenWinograd 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
Change History (49)
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 9 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
comment:4 followup: ↓ 6 Changed 9 years ago by
The patch applies neither cleanly to 4.8 nor 5.0.beta6. The issue 4.8 is small and easy to fix, 5.0.beta6 are a bit more failures.
comment:5 Changed 9 years ago by
comment:6 in reply to: ↑ 4 Changed 9 years ago by
Replying to malb:
The patch applies neither cleanly to 4.8 nor 5.0.beta6. The issue 4.8 is small and easy to fix, 5.0.beta6 are a bit more failures.
I get
(sage subshell) mpc721:sage king$ hg qpush applying trac12103_meataxe_rel11900.patch patching file sage/modules/quotient_module.py Hunk #12 succeeded at 297 with fuzz 1 (offset 10 lines). Hunk #13 succeeded at 322 with fuzz 1 (offset 14 lines). now at: trac12103_meataxe_rel11900.patch SAGE_ROOT=/home/king/SAGE/sage5.0.beta6
So, I can not confirm that the first tobeapplied patch is really problematic (ok, fuzz 1 might be fixed at some point, but I don't get actual errors).
How can I test in module_list.py whether or not MeatAxe
is installed? I suppose the patch to the sage library should not be applied by the installation script of the spkg.
comment:7 Changed 9 years ago by
comment:8 followup: ↓ 9 Changed 9 years ago by
Ah, crap, 11900 was it.
RE: module_list.py I commented on it here: https://bitbucket.org/malb/sagemath/pullrequest/1/12103meataxewrapper#comment3510
PS: Did you get my email that I sent to simon.king_unijena.de?
comment:9 in reply to: ↑ 8 Changed 9 years ago by
 Description modified (diff)
Replying to malb:
Ah, crap, 11900 was it.
OK, I changed the instructions in the ticket description accordingly.
RE: module_list.py I commented on it here: https://bitbucket.org/malb/sagemath/pullrequest/1/12103meataxewrapper#comment3510
PS: Did you get my email that I sent to simon.king_unijena.de?
Yes, but I didn't look at bitbucket yet, and I suppose I will not find the time to start and learn the new development before Monday.
comment:10 Changed 8 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:11 Changed 7 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:12 Changed 7 years ago by
 Status changed from needs_review to needs_work
comment:13 Changed 7 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:14 Changed 7 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:15 Changed 6 years ago by
I think this ticket should be revived. But the aim should be to have a library version of the *latest* MeatAxe upstream sources. And of course it should be a newstyle package.
comment:16 Changed 6 years ago by
 Description modified (diff)
comment:17 Changed 6 years ago by
 Cc jdemeyer vbraun added; mringe@… david.green@… removed
The first step will probably be the creation of a newstyle package for MeatAxe 2.4.24 (which I take as an exercise for learning newstyle packaging).
The README file says:
================================================================================ INSTALLATION (for Unix systems) ================================================================================ 1) Copy Makefile.conf.dist to Makefile.conf. Edit Makefile.conf and fill in the necessary parameters. 2) To compile all programs an run the test suite, enter make check You will probably need gmake (GNU make) to build the MeatAxe. 3) If there were no errors, run make install to install the executables in their final location (as selected in the makefile).
I wonder if we should follow that procedure. After all, Makefile.conf.dist
just defines a couple of variables that determine the compiler, the flags, the location of the binaries, the location of the library and the implementation (for fields of order up to 255 or for larger fields).
What do people think?
 a) Should we patch Makefile, by removing the line
include Makefile.conf
, and define all the variables MTXLIB, MTXBIN etc. from Makefile.conf as environment variables?
or
 b) Should we keep Makefile, create an empty Makefile.conf, and do the rest with environment variables?
or
 Should spkginstall first create a fully grown Makefile.conf?
comment:18 Changed 6 years ago by
If all you have to do is touch Makefile.conf
then I'd go for that.
comment:19 Changed 6 years ago by
 Component changed from linear algebra to packages: experimental
comment:20 Changed 6 years ago by
I am slightly puzzled.
There is a variable ZZZ used in Makefile. But when I do
ZZZ=0 $MAKE
then apparently Makefile doesn't know about ZZZ. What do I need to do to define ZZZ so that Makefile knows about it?
comment:21 Changed 6 years ago by
Unless you export ZZZ
it is not passed to subprocesses. Alternatively, you might want to use $MAKE ZZZ=0
.
comment:22 followups: ↓ 23 ↓ 25 ↓ 26 Changed 6 years ago by
Thanks, "export" did the trick.
However, I am afraid that some of the reasons for massively patching MeatAxe 2.2.4 are still present in version 2.4.24:
 The environment variables MTXLIB and MTXBIN are ignored during build. I.e., the library is put into ./tmp/, the binaries are put into ./bin/
Suggested solution: Let spkginstall move the created binaries and libmtx.a to the desired location
make clean
doesn't work, as it also goes into the directory test/ and callsmake clean
therebut there is no test/Makefile.
Not relevant here, as the build directory is deleted anyway.
make check
rebuilds everything in ./tmp/ and ./bin/ before testing. Hence, the test suite actually does NOT test what is in $SAGE_ROOT/local/lib and $SAGE_ROOT/local/bin.
Question on make check
: Would it be OK to let spkginstall ALWAYS do make check
? Or should that be solely the job of spkgcheck (with the drawback that then spkgcheck would rebuild meataxe)?
comment:23 in reply to: ↑ 22 Changed 6 years ago by
Replying to SimonKing:
Question on
make check
: Would it be OK to let spkginstall ALWAYS domake check
? Or should that be solely the job of spkgcheck (with the drawback that then spkgcheck would rebuild meataxe)?
Or should spkginstall test whether SAGE_CHECK=yes, and choose between make
and make check
accordingly?
comment:24 Changed 6 years ago by
Do I understand correctly that for automatically downloading the sources from upstream, I should create spkgsrc similarly to what I find in build/pkg/singular/spkgsrc?
comment:25 in reply to: ↑ 22 ; followup: ↓ 32 Changed 6 years ago by
Replying to SimonKing:
However, I am afraid that some of the reasons for massively patching MeatAxe 2.2.4 are still present in version 2.4.24:
But one aspect has improved: MeatAxe used to rely on certain tables that were put (and when needed also created) in the current directory. And I had to patch the csources so that MeatAxe would be able to find the tables in a fixed directory. Now I cannot see any of these tables.
comment:26 in reply to: ↑ 22 Changed 6 years ago by
Replying to SimonKing:
Question on
make check
: Would it be OK to let spkginstall ALWAYS domake check
? Or should that be solely the job of spkgcheck (with the drawback that then spkgcheck would rebuild meataxe)?
In my opinion, if make check
doesn't add too much time (a minute?) to the build, then you can always do it, but if it's more than that, it should be done only in spkgcheck
.
comment:27 Changed 6 years ago by
You don't need spkgsrc, its just a bandaid to modify tarballs (don't do it if you can avoid it)
comment:28 Changed 6 years ago by
 Branch set to u/SimonKing/meataxe
comment:29 Changed 6 years ago by
 Commit set to e732f0ee8fa0dc631f9cffd62b4dd1f6f2c10c2d
 Description modified (diff)
New commits:
e732f0e  An optional MeatAxe package

comment:30 Changed 6 years ago by
Question on how to continue:
My aim is to provide a Cython wrapper, so, I need to copy meataxe.h to some include location.
But how to deal with the Cython wrapper? Apparently it would be in the Sage library, but apparently it will not compile if meataxe is not installed.
So, should the package install the cython code into the Sage library? Or is it possible to have code permanently in the Sage library that is only compiled if a certain package is installed, and otherwise is left untouched?
comment:31 Changed 6 years ago by
PS: Note that MeatAxe has a nice documentation, and as usual it is installed if SAGE_SPKG_INSTALL_DOCS=yes.
comment:32 in reply to: ↑ 25 ; followup: ↓ 33 Changed 6 years ago by
Replying to SimonKing:
But one aspect has improved: MeatAxe used to rely on certain tables that were put (and when needed also created) in the current directory. And I had to patch the csources so that MeatAxe would be able to find the tables in a fixed directory. Now I cannot see any of these tables.
I am afraid I stand corrected. Meanwhile I have a Cython wrapper on my laptop, and when I create a matrix over GF(2), then a file p002.zzz (defining multiplication table) is created in the current directory.
That's a very nasty property of MeatAxe. What shall we do about it?
Shall we leave it like that?
Shall I try to port my patch from 2.2.4 to 2.4.24 and ensure that all multiplication tables should be created in SAGE_ROOT/local/lib/meataxe/?
comment:33 in reply to: ↑ 32 Changed 6 years ago by
Replying to SimonKing:
Shall I try to port my patch from 2.2.4 to 2.4.24 and ensure that all multiplication tables should be created in SAGE_ROOT/local/lib/meataxe/?
If "yes": Where shall the tables be placed? In SAGE_LOCAL/share/meataxe/ perhaps?
comment:34 Changed 6 years ago by
From the MeatAxe sources:
/** ** MeatAxe Library Directory. ** This variable contains the name of the MeatAxe library directory. ** Arithmetic table files are searched in this directory. The value of ** MtxLibDir can be set on the command line with the "L" option. Otherwise, ** the value of the environment variable MTXLIB is used. If neither "L" nor ** MTXLIB are defined, the default directory, which was selected when ** building the MeatAxe, is used. ** @see MtxBinDir **/
So, apparently the multiplication tables are supposed to be in MTXLIB. But that has NEVER worked for me.
Or rather, it could be that MTXLIB has to be an environment variable at running time. Would it be acceptable that a module sage.matrix.meataxe
sets an environment variable for MeatAxe? I'll test if that works.
comment:35 Changed 6 years ago by
PS: It says "Otherwise, the value of the environment variable MTXLIB is used." That definitely does not work.
comment:36 Changed 6 years ago by
Setting the environment variable at running time doesn't work either. That's a bug that has always been present in MeatAxe. So, I guess I need to patch the sources.
comment:37 Changed 6 years ago by
Internally, MeatAxe stores MTXLIB in MtxLibDir?. But directly defining MtxLibDir? at run time didn't help. Sigh.
comment:38 Changed 6 years ago by
 Commit changed from e732f0ee8fa0dc631f9cffd62b4dd1f6f2c10c2d to 6c324700abeb37c3e32ebf36c7cf9027c8e70588
Branch pushed to git repo; I updated commit sha1. New commits:
71c9b94  Install meataxe header; no separate meataxe folder in SAGE_LOCAL/lib/

0320de9  Declare that meataxe is an optional package

e0ca6d0  Use fPIC for creating libmtx.a

6e6cdd8  Choose a location for multiplication tables

6c32470  Patch MeatAxe so that MTXLIB is used to store library files

comment:39 followup: ↓ 41 Changed 6 years ago by
You shouldn't assume that the Sage directory is writeable. So the multiplication tables should be stored in SAGE_TMP
or (if you want to keep them) in some other subdirectory of DOT_SAGE
, probably DOT_SAGE/meataxe2.4.24/
.
comment:40 Changed 6 years ago by
Recent changes:
 Since we want to wrap the code, it is needed to make the meataxe header available.
 I found that packages are supposed to give a file called "type". I declare there that the package is supposed to be optional.
 Since we move libmtx.a from a temporary location to somewhere in SAGE_LOCAL, it is needed to use "fPIC".
 The multiplication tables shouldn't pollute the user's current directory. I propose to store them in SAGE_SHARE/meataxe/.
 MeatAxe has IOfunctions that accept an argument saying that the file is a library filebut in the IOfunctions, it is always first looked into the current directory, and the library location is only considered if the current directory didn't work.
 In at least one function, the IOargument for "library files" is used wrongly. So, after fixing the IOfunction, the wrong argument needed to be fixed, too.
In meataxe/patches is a patch that fixes these two upstream bugs.
Current status:
 The package builds fine.
 When running the testsuite, I sometimes see a wrong checksum, but when I repeat the testsuite, everything is fine. I guess upstream's checksum function is fragile. Not sure if I'm going to fix that.
 With the Cython wrapper on my laptop, I can create MeatAxe matrices in a Sage session, and the current directory is not polluted by multiplication tables.
TODO:
 Finish the Cython wrapper.
comment:41 in reply to: ↑ 39 ; followup: ↓ 43 Changed 6 years ago by
Replying to jhpalmieri:
You shouldn't assume that the Sage directory is writeable. So the multiplication tables should be stored in
SAGE_TMP
or (if you want to keep them) in some other subdirectory ofDOT_SAGE
, probablyDOT_SAGE/meataxe2.4.24/
.
Right, that could be a problem. The tables should indeed be permanent. So, DOT_SAGE/meataxe
(without version number) it is.
comment:42 Changed 6 years ago by
 Commit changed from 6c324700abeb37c3e32ebf36c7cf9027c8e70588 to d9675fbca6cf8647548f6f37522d2c388812669d
Branch pushed to git repo; I updated commit sha1. New commits:
d9675fb  Use DOT_SAGE, not SAGE_LOCAL, for storing multiplication tables

comment:43 in reply to: ↑ 41 ; followup: ↓ 44 Changed 6 years ago by
Replying to SimonKing:
Replying to jhpalmieri:
You shouldn't assume that the Sage directory is writeable. So the multiplication tables should be stored in
SAGE_TMP
or (if you want to keep them) in some other subdirectory ofDOT_SAGE
, probablyDOT_SAGE/meataxe2.4.24/
.Right, that could be a problem. The tables should indeed be permanent. So,
DOT_SAGE/meataxe
(without version number) it is.
As long as you're pretty confident that the tables will be compatible with future versions. (We ran into this problem with IPython
and matplotlib
, which is why their directories in DOT_SAGE
include the version number.)
comment:44 in reply to: ↑ 43 ; followup: ↓ 45 Changed 6 years ago by
Replying to jhpalmieri:
As long as you're pretty confident that the tables will be compatible with future versions. (We ran into this problem with
IPython
andmatplotlib
, which is why their directories inDOT_SAGE
include the version number.)
The format hasn't changed since version 2.2.3, and the current version already is 4 years old. So, I don't think there will be changes any time soon.
Moreover, if we really need to change it, we can create all multiplication tables (we have bounded field size) in a fraction of a second during package installation.
comment:45 in reply to: ↑ 44 Changed 6 years ago by
Replying to SimonKing:
Moreover, if we really need to change it, we can create all multiplication tables (we have bounded field size) in a fraction of a second during package installation.
Aaahm, if we use SAGE_SHARE.
Anyway, if things really go bad in future meataxe versions, it should be possible to patch it so that invalid old multiplication tables are automatically removed when accidentally opening them.
comment:46 Changed 6 years ago by
 Description modified (diff)
Here is more on
libmeataxe1.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 libmeataxe1.0.spkg). I wrap the C library using Cython (this is trac12103_meataxe.patch)MeatAxe
uses school book multiplication. I added StrassenWinograd 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 libmeataxe1.0.spkg
would automatically patch the Sage library. Question to Sage experts: Is that possible?Anyway, I think it can be reviewed...