#12103: Use MeatAxe as an optional back end for dense matrices over `GF(p^n)`, p
odd, n>1, `p^n<255`
------------------------------+---------------------------------------------
Reporter: SimonKing | Owner: jason, was
Type: defect | Status: needs_review
Priority: major | Milestone: sage-4.8
Component: linear algebra | Keywords: linear algebra, MeatAxe
Work_issues: | Upstream: None of the above - read trac
for reasoning.
Reviewer: | Author: Simon King
Merged: | Dependencies: #9562 #4260
------------------------------+---------------------------------------------
Changes (by SimonKing):
* status: new => needs_review
Old description:
> 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
> [http://sage.math.washington.edu/home/SimonKing/LibMeatAxe/libmeataxe-1.0.spkg
> the optional libmeataxe spkg]
> * Apply either [attachment:] or [attachment:], depending on whether or
> not you have #11900 applied.
New description:
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
[http://sage.math.washington.edu/home/SimonKing/LibMeatAxe/libmeataxe-1.0.spkg
the optional libmeataxe spkg]
* Apply either [attachment:trac12103_meataxe.patch] or
[attachment:trac12103_meataxe_rel11900.patch], depending on whether or not
you have #11900 applied.
--
Comment:
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
[http://sage.math.washington.edu/home/SimonKing/LibMeatAxe/libmeataxe-1.0.spkg
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...
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12103#comment:1>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
