#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 | 20a16e18db945d6e123f457a44ee5835427a1351
- read trac for reasoning. | Stopgaps:
Branch: |
u/SimonKing/meataxe |
Dependencies: #9562 #4260 |
-------------------------------------+-------------------------------------
Comment (by SimonKing):
In the recent commit, patches `StrassenWinogradImplementation.patch` and
`StrassenWinogradUsage.patch` are provided.
There, I implement the Winograd-Strassen multiplication algorithm in
!MeatAxe. I optimized the cutoff parameter using a Cython wrapper that I
didn't post yet (needs doctests and needs to wrap echelonisation).
I tested on matrices of different sizes and different fields. First of
all, the school book multiplication in !MeatAxe is vastly faster than the
current matrix multiplication in Sage for all non-prime finite fields of
odd characteristic (of course with field order < 256).
Moreover, it turns out that the Winograd-Strassen implementation is not
only asymptotically fast, but even on small examples (200x200) is as fast
as !MeatAxe's school book multiplication. So, I think it makes sense to
use it not only in my Cython wrapper but also in the !MeatAxe
functions/executables, which is done in `StrassenWinogradUsage.patch`.
The fact that !MeatAxe's test suite still works is an indicative that my
Winograd-Strassen implementation ok.
Of course it will be even clearer in the Cython wrapper that will be
subject of the next commit. Then, I'll show timings.
--
Ticket URL: <http://trac.sagemath.org/ticket/12103#comment:48>
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.
