Opened 10 years ago

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

Reported by: Owned by: SimonKing jason, was major sage-7.0 packages: optional linear algebra, MeatAxe malb, jdemeyer, vbraun Simon King Reported upstream. No feedback yet. #9562 #4260

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

### comment:1 Changed 10 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 10 years ago by SimonKing

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

### Changed 10 years ago by SimonKing

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

### comment:2 Changed 10 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 9 years ago by SimonKing

Fix one doctest (coping with a changed class name)

### comment:3 Changed 9 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: ↓ 6 Changed 9 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 9 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 9 years ago by SimonKing

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 9 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: ↓ 9 Changed 9 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 9 years ago by SimonKing

• Description modified (diff)