#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_work
Priority: major | Milestone: sage-6.4
Component: packages: | Resolution:
experimental | Merged in:
Keywords: linear algebra, | Reviewers:
MeatAxe | Work issues:
Authors: Simon King | Commit:
Report Upstream: None of the above | e732f0ee8fa0dc631f9cffd62b4dd1f6f2c10c2d
- read trac for reasoning. | Stopgaps:
Branch: |
u/SimonKing/meataxe |
Dependencies: #9562 #4260 |
-------------------------------------+-------------------------------------
Changes (by SimonKing):
* commit: => e732f0ee8fa0dc631f9cffd62b4dd1f6f2c10c2d
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`.
>
> 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.
>
> 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__'''
>
> * Install
> [http://sage.math.washington.edu/home/SimonKing/LibMeatAxe/libmeataxe-1.0.spkg
> the optional libmeataxe spkg]
> * Apply [attachment:trac12103_meataxe_rel11900.patch]
> * Apply [attachment:trac12103_meataxe_docfix.patch]
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`.
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__'''
* Install
[http://sage.math.washington.edu/home/SimonKing/LibMeatAxe/libmeataxe-1.0.spkg
the optional libmeataxe spkg]
* Apply [attachment:trac12103_meataxe_rel11900.patch]
* Apply [attachment:trac12103_meataxe_docfix.patch]
--
Comment:
New commits:
||[http://git.sagemath.org/sage.git/commit/?id=e732f0ee8fa0dc631f9cffd62b4dd1f6f2c10c2d
e732f0e]||{{{An optional MeatAxe package}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/12103#comment:29>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
