#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 | 539b1349359004b78712a67d2739cce9ce0227da
- read trac for reasoning. | Stopgaps:
Branch: |
u/SimonKing/meataxe |
Dependencies: #9562 #4260 |
-------------------------------------+-------------------------------------
Comment (by SimonKing):
The last commit really isn't finished yet (most tests and much
documentation is missing). But for now it is enough to demonstrate the
progress compared with the current Sage beta.
Please make sure that you use attachment:meataxe-2.4.24.tar.gz, not the
source tarball from the upstream download page.
In the latest development version, we have
{{{
sage: MS = MatrixSpace(GF(5^3,'y'),2000)
sage: %time A = MS.random_element()
CPU times: user 6.71 s, sys: 20 ms, total: 6.73 s
Wall time: 6.79 s
sage: type(A)
<type 'sage.matrix.matrix_generic_dense.Matrix_generic_dense'>
sage: B = MS.random_element()
sage: %time A*B
CPU times: user 23min 49s, sys: 490 ms, total: 23min 50s
Wall time: 23min 55s # using 7.5% of my computer's memory
2000 x 2000 dense matrix over Finite Field in y of size 5^3 (use the
'.str()' method to see the entries)
sage: %time ~A
CPU times: user 23min 42s, sys: 842 ms, total: 23min 43s
Wall time: 23min 47s # using 11.3% of my computer's memory
2000 x 2000 dense matrix over Finite Field in y of size 5^3 (use the
'.str()' method to see the entries)
}}}
23 minutes for a single multiplication or inversion of a not so big matrix
over a small field!!
You see why I see the need of a different backend?
Here is the same example when the optional meataxe package (and its
wrapper) is used:
{{{
sage: MS = MatrixSpace(GF(5^3,'y'),2000)
sage: %time A = MS.random_element()
CPU times: user 320 ms, sys: 5 ms, total: 325 ms
Wall time: 351 ms
sage: type(A)
<type 'sage.matrix.matrix_modpn_dense.Matrix_modpn_dense'>
sage: B = MS.random_element()
sage: %time A*B # using 4.8% of my computer's memory
CPU times: user 14.4 s, sys: 1 ms, total: 14.4 s
Wall time: 14.4 s
2000 x 2000 dense matrix over Finite Field in y of size 5^3 (use the
'.str()' method to see the entries)
sage: %time ~A # using 5.9% of my computer's memory
CPU times: user 32.7 s, sys: 69 ms, total: 32.8 s
Wall time: 33.2 s
2000 x 2000 dense matrix over Finite Field in y of size 5^3 (use the
'.str()' method to see the entries)
sage: %time _*A == A*_ == 1
CPU times: user 28.7 s, sys: 60 ms, total: 28.8 s
Wall time: 29 s
True
}}}
The last example indicates that the (Strassen) multiplication is vastly
faster than what we have now in Sage.
Admittedly, the patched !MeatAxe is still a lot slower than linbox for
prime fields or M4RIE for characteristic 2. That's why I only suggest to
use it for non-prime fields of odd characteristic.
By the way, !MeatAxe is supposed to have a different kernel for fields of
size > 255. But strangely, the respective source file is not in the
upstream source tarball.
--
Ticket URL: <http://trac.sagemath.org/ticket/12103#comment:67>
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.
