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 29

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: u/SimonKing/meataxe (Commits) Commit: e732f0ee8fa0dc631f9cffd62b4dd1f6f2c10c2d
Dependencies: #9562 #4260 Stopgaps:

Description (last modified by SimonKing)

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.rwth-aachen.de/~MTX/meataxe-2.4.24.tar.gz

What is done

There is no spkg-check. 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 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

Change History (32)

comment:1 Changed 9 years ago by SimonKing

  • Description modified (diff)
  • Status changed from new to needs_review

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 with MeatAxe 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 file patches/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:

  • Normally, 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. See src/src/window.c.
  • The environment variable MTXLIB was supposed to tell MeatAxe 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.
  • A simpler version of the package has been part of our group cohomology spkg. Bad experiences on Solaris made me change three names: I changed
    • T_STRING into T_STRINGS,
    • matextract into _matextract,
    • matid into MTXmatid.

Please don't ask me why the Solaris linker was mistaking these symbols with symbols in completely different Sage packages, but as a matter of fact it did.

The aim of this ticket is to make the modified MeatAxe an optional back end for dense matrices over GF(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...

Changed 9 years ago by SimonKing

Use MeatAxe as back end for linear algebra over some finite fields.

Changed 9 years ago by SimonKing

Use MeatAxe as back end for linear algebra over some finite fields. Relative to #11900

comment:2 Changed 9 years ago by SimonKing

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]

Changed 8 years ago by SimonKing

Fix one doctest (coping with a changed class name)

comment:3 Changed 8 years ago by SimonKing

  • 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 follow-up: Changed 8 years ago by 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.

comment:5 Changed 8 years ago by malb

as of now module_list.py will try to build matrix_modpn_dense regardless of whether MeatAxe? is installed, but it should only build it if MeatAxe? is installed.

comment:6 in reply to: ↑ 4 Changed 8 years ago by SimonKing

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/sage-5.0.beta6

So, I can not confirm that the first to-be-applied 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 8 years ago by SimonKing

PS: Martin, did you really try to apply trac12103_meataxe_rel11900.patch? Namely, the previous patch (that is not relative to #11900) should be disregarded, as #11900 is already merged.

comment:8 follow-up: Changed 8 years ago by malb

Ah, crap, 11900 was it.

RE: module_list.py I commented on it here: https://bitbucket.org/malb/sagemath/pull-request/1/12103-meataxe-wrapper#comment-3510

PS: Did you get my e-mail that I sent to simon.king_uni-jena.de?

comment:9 in reply to: ↑ 8 Changed 8 years ago by SimonKing

  • 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/pull-request/1/12103-meataxe-wrapper#comment-3510

PS: Did you get my e-mail that I sent to simon.king_uni-jena.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 7 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:11 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:12 Changed 6 years ago by rws

  • Status changed from needs_review to needs_work

comment:13 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:14 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:15 Changed 5 years ago by SimonKing

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 new-style package.

comment:16 Changed 5 years ago by SimonKing

  • Description modified (diff)

comment:17 Changed 5 years ago by SimonKing

  • Cc jdemeyer vbraun added; mringe@… david.green@… removed

The first step will probably be the creation of a new-style package for MeatAxe 2.4.24 (which I take as an exercise for learning new-style 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?

  1. 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

  1. b) Should we keep Makefile, create an empty Makefile.conf, and do the rest with environment variables?

or

  1. Should spkg-install first create a fully grown Makefile.conf?

comment:18 Changed 5 years ago by vbraun

If all you have to do is touch Makefile.conf then I'd go for that.

comment:19 Changed 5 years ago by SimonKing

  • Component changed from linear algebra to packages: experimental

comment:20 Changed 5 years ago by SimonKing

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 5 years ago by vbraun

Unless you export ZZZ it is not passed to subprocesses. Alternatively, you might want to use $MAKE ZZZ=0.

comment:22 follow-ups: Changed 5 years ago by SimonKing

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 spkg-install 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 calls make clean there---but 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 spkg-install ALWAYS do make check? Or should that be solely the job of spkg-check (with the drawback that then spkg-check would rebuild meataxe)?

comment:23 in reply to: ↑ 22 Changed 5 years ago by SimonKing

Replying to SimonKing:

Question on make check: Would it be OK to let spkg-install ALWAYS do make check? Or should that be solely the job of spkg-check (with the drawback that then spkg-check would rebuild meataxe)?

Or should spkg-install test whether SAGE_CHECK=yes, and choose between make and make check accordingly?

comment:24 Changed 5 years ago by SimonKing

Do I understand correctly that for automatically downloading the sources from upstream, I should create spkg-src similarly to what I find in build/pkg/singular/spkg-src?

comment:25 in reply to: ↑ 22 Changed 5 years ago by SimonKing

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 c-sources 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 5 years ago by jhpalmieri

Replying to SimonKing:

Question on make check: Would it be OK to let spkg-install ALWAYS do make check? Or should that be solely the job of spkg-check (with the drawback that then spkg-check 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 spkg-check.

comment:27 Changed 5 years ago by vbraun

You don't need spkg-src, its just a bandaid to modify tarballs (don't do it if you can avoid it)

comment:28 Changed 5 years ago by SimonKing

  • Branch set to u/SimonKing/meataxe

comment:29 Changed 5 years ago by SimonKing

  • Commit set to e732f0ee8fa0dc631f9cffd62b4dd1f6f2c10c2d
  • Description modified (diff)

New commits:

e732f0eAn optional MeatAxe package
Note: See TracTickets for help on using tickets.