Use MeatAxe as an optional back end for dense matrices over `GF(p^n)`, p odd, n>1, `p^n<255` #12103

simon-king-jena · 2011-11-30T12:55:11Z

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

The upstream sources http://www.math.rwth-aachen.de/~MTX/meataxe-2.4.24.tar.gz needed to be repackaged, in order to unpack into a single folder. Use attachment: 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

Depends on #19240

Upstream: Reported upstream. No feedback yet.

CC: @malb @jdemeyer @vbraun

Component: packages: optional

Keywords: MeatAxe

Author: Simon King

Branch: 74edf19

Reviewer: Jeroen Demeyer, Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/12103

The text was updated successfully, but these errors were encountered:

simon-king-jena · 2011-11-30T13:28:11Z

comment:1

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 attachment: 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...

simon-king-jena · 2011-12-01T11:23:02Z

Attachment: trac12103_meataxe.patch.gz

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

simon-king-jena · 2011-12-01T11:23:36Z

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

simon-king-jena · 2011-12-01T11:25:11Z

comment:2

Attachment: trac12103_meataxe_rel11900.patch.gz

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]

simon-king-jena · 2012-03-03T14:02:57Z

Attachment: trac12103_meataxe_docfix.patch.gz

Fix one doctest (coping with a changed class name)

simon-king-jena · 2012-03-03T14:06:11Z

comment:3

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

malb · 2012-03-03T15:26:02Z

comment:4

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.

malb · 2012-03-03T15:27:21Z

comment:5

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.

simon-king-jena · 2012-03-03T16:12:35Z

comment:6

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.

simon-king-jena · 2012-03-03T16:13:55Z

comment:7

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.

malb · 2012-03-03T16:16:53Z

comment:8

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?

simon-king-jena · 2012-03-03T16:20:34Z

comment:9

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.

vbraun · 2015-10-11T22:14:27Z

comment:163

not access to port 22 == no access to the internet. Complain to whoever is blocking you that you can't do your work and their service is useless to you

sagetrac-git · 2015-10-12T09:44:28Z

Branch pushed to git repo; I updated commit sha1. New commits:

`c67cb42`	`Fix pickling of meataxe matrices`

sagetrac-git · 2015-10-12T09:44:28Z

Changed commit from 710668d to c67cb42

simon-king-jena · 2015-10-12T10:09:28Z

comment:165

The problem was: The default implementation of unpickling relies on set_unsafe(i,j,val). In my implementation, set_unsafe relies on a converter from finite field elements to the internal representation---and the converter is not created during the unpickling.

Hence, I created a custom __reduce__ relying on some unpickling function.

There, I used the occasion to return to what I did in the old group cohomology spkg: Pickling is not by conversion of the matrix to a list of entries, but it dumps the densely packed internal representation. Advantage: It is a lot faster!

For the group cohomology spkg, it was checked that the internal representation does not depend on details such as big versus little endian machines: A pickle created on a big-endian machine can correctly be unpickled with a little-endian machine.

Another advantage of the new approach will be apparent in #18514: Since the new pickling/unpickling scheme for meataxe matrices is a lot closer to the scheme used in the old group cohomology spkg, the new group cohomology package should relatively easily be able to read data from existing cohomology data bases.

simon-king-jena · 2015-10-12T10:09:28Z

Changed work issues from Pickling to none

tscrim · 2015-12-16T20:56:34Z

comment:166

I get 2 doctest failures with MeatAxe not installed. Both I think are because they should be marked optional:

File "../../matrix/matrix_gfpn_dense.pyx", line 213, in sage.matrix.matrix_gfpn_dense.PrimeFieldConverter_class.int_to_field
Failed example:
    C.int_to_field(int(2))
Exception raised:
    Traceback (most recent call last):
      File "/home/travis/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 496, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/travis/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 858, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.matrix.matrix_gfpn_dense.PrimeFieldConverter_class.int_to_field[1]>", line 1, in <module>
        C.int_to_field(int(Integer(2)))
    NameError: name 'C' is not defined

**********************************************************************

File "../../matrix/matrix_space.py", line 992, in sage.matrix.matrix_space.MatrixSpace._get_matrix_class
Failed example:
    type(matrix(GF(125,'z'), 2, range(4)))
Expected:
    <type 'sage.matrix.matrix_gfpn_dense.Matrix_gfpn_dense'>
Got:
    <type 'sage.matrix.matrix_generic_dense.Matrix_generic_dense'>

tscrim · 2015-12-16T20:58:22Z

comment:167

However, all tests pass in src/matrix with it installed.

sagetrac-git · 2016-01-16T13:05:44Z

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

`c2e6fe5`	`A full wrapper for MeatAxe matrices`
`395aa9a`	`Improve echelon computation in MeatAxe, and fix some compiler warnings`
`c5f328c`	`Doctests and error handling for MeatAxe`
`c29d1f8`	`Fix computation of row-reduced echelon form`
`f816e41`	`Fix doctests when meataxe is installed`
`80af75e`	`Use and propagate specific return values on error in matrix-related MeatAxe functions.`
`6649c82`	`Remove overcautious commands in spkg-install; rely on default error return values in matrix_gfpn_dense`
`d24260c`	`Fix pickling of meataxe matrices`
`bddc09d`	`Merge branch 'u/SimonKing/meataxe' of trac.sagemath.org:sage into t/12103/meataxe`
`74edf19`	`Make two doctests optional`

sagetrac-git · 2016-01-16T13:05:44Z

Changed commit from c67cb42 to 74edf19

simon-king-jena · 2016-01-16T13:07:20Z

comment:169

I made the two failing tests optional and at that occasion merged the latest develop.

Is it fine now?

tscrim · 2016-01-16T15:44:46Z

comment:170

Looks good to me now. Thanks.

tscrim · 2016-01-16T15:44:46Z

Reviewer: Jeroen Demeyer, Travis Scrimshaw

vbraun · 2016-01-20T10:20:08Z

Changed branch from u/SimonKing/meataxe to 74edf19

dimpase · 2016-02-24T23:26:50Z

Changed commit from 74edf19 to none

dimpase · 2016-02-24T23:26:50Z

comment:172

there is no tarball on the mirrors, apparently

vbraun · 2016-02-25T09:34:58Z

comment:173

Fixed

simon-king-jena added this to the sage-5.11 milestone Nov 30, 2011

simon-king-jena added c: linear algebra labels Nov 30, 2011

simon-king-jena assigned jasongrout and williamstein Nov 30, 2011

This comment has been minimized.

Sign in to view

simon-king-jena added the s: needs review label Nov 30, 2011

This comment has been minimized.

Sign in to view

jdemeyer modified the milestones: sage-5.11, sage-5.12 Aug 13, 2013

sagetrac-vbraun-spam mannequin modified the milestones: sage-6.1, sage-6.2 Jan 30, 2014

rwst added s: needs work and removed s: needs review labels Mar 31, 2014

sagetrac-vbraun-spam mannequin removed this from the sage-6.2 milestone May 6, 2014

simon-king-jena added s: needs review and removed s: needs work labels Oct 12, 2015

tscrim modified the milestones: sage-6.9, sage-7.0 Dec 16, 2015

tscrim added s: needs work and removed s: needs review labels Dec 16, 2015

simon-king-jena added s: needs review and removed s: needs work labels Jan 16, 2016

tscrim added s: positive review and removed s: needs review labels Jan 16, 2016

vbraun removed the s: positive review label Jan 20, 2016

vbraun closed this as completed in 1c94fa3 Jan 20, 2016

simon-king-jena mentioned this issue Aug 17, 2016

Prime slicing for matrix multiplication #12177

Open

jhpalmieri mentioned this issue May 10, 2021

Archive superseded/broken old-style packages #19220

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Use MeatAxe as an optional back end for dense matrices over `GF(p^n)`, p odd, n>1, `p^n<255` #12103

Use MeatAxe as an optional back end for dense matrices over `GF(p^n)`, p odd, n>1, `p^n<255` #12103

simon-king-jena commented Nov 30, 2011

This comment has been minimized.

simon-king-jena commented Nov 30, 2011

simon-king-jena commented Dec 1, 2011

simon-king-jena commented Dec 1, 2011

simon-king-jena commented Dec 1, 2011

simon-king-jena commented Mar 3, 2012

This comment has been minimized.

simon-king-jena commented Mar 3, 2012

malb commented Mar 3, 2012

malb commented Mar 3, 2012

simon-king-jena commented Mar 3, 2012

simon-king-jena commented Mar 3, 2012

malb commented Mar 3, 2012

simon-king-jena commented Mar 3, 2012

This comment has been minimized.

vbraun commented Oct 11, 2015

sagetrac-git mannequin commented Oct 12, 2015

sagetrac-git mannequin commented Oct 12, 2015

simon-king-jena commented Oct 12, 2015

simon-king-jena commented Oct 12, 2015

tscrim commented Dec 16, 2015

tscrim commented Dec 16, 2015

sagetrac-git mannequin commented Jan 16, 2016

sagetrac-git mannequin commented Jan 16, 2016

simon-king-jena commented Jan 16, 2016

tscrim commented Jan 16, 2016

tscrim commented Jan 16, 2016

vbraun commented Jan 20, 2016

dimpase commented Feb 24, 2016

dimpase commented Feb 24, 2016

vbraun commented Feb 25, 2016

Use MeatAxe as an optional back end for dense matrices over GF(p^n), p odd, n>1, p^n<255 #12103

Use MeatAxe as an optional back end for dense matrices over GF(p^n), p odd, n>1, p^n<255 #12103

Comments

simon-king-jena commented Nov 30, 2011

This comment has been minimized.

simon-king-jena commented Nov 30, 2011

simon-king-jena commented Dec 1, 2011

simon-king-jena commented Dec 1, 2011

simon-king-jena commented Dec 1, 2011

simon-king-jena commented Mar 3, 2012

This comment has been minimized.

simon-king-jena commented Mar 3, 2012

malb commented Mar 3, 2012

malb commented Mar 3, 2012

simon-king-jena commented Mar 3, 2012

simon-king-jena commented Mar 3, 2012

malb commented Mar 3, 2012

simon-king-jena commented Mar 3, 2012

This comment has been minimized.

vbraun commented Oct 11, 2015

sagetrac-git mannequin commented Oct 12, 2015

sagetrac-git mannequin commented Oct 12, 2015

simon-king-jena commented Oct 12, 2015

simon-king-jena commented Oct 12, 2015

tscrim commented Dec 16, 2015

tscrim commented Dec 16, 2015

sagetrac-git mannequin commented Jan 16, 2016

sagetrac-git mannequin commented Jan 16, 2016

simon-king-jena commented Jan 16, 2016

tscrim commented Jan 16, 2016

tscrim commented Jan 16, 2016

vbraun commented Jan 20, 2016

dimpase commented Feb 24, 2016

dimpase commented Feb 24, 2016

vbraun commented Feb 25, 2016

Use MeatAxe as an optional back end for dense matrices over `GF(p^n)`, p odd, n>1, `p^n<255` #12103

Use MeatAxe as an optional back end for dense matrices over `GF(p^n)`, p odd, n>1, `p^n<255` #12103