#8096: Speed up parent creation for multiplication of square matrices
---------------------------------------+------------------------------------
Reporter: boothby | Owner: boothby
Type: enhancement | Status: needs_info
Priority: minor | Milestone:
Component: linear algebra | Keywords:
Work_issues: various doc test errors | Upstream: N/A
Reviewer: | Author: boothby, robertwb
Merged: | Dependencies:
---------------------------------------+------------------------------------
Changes (by SimonKing):
* status: needs_work => needs_info
Comment:
Here is another data point concerning slowness - ridiculous slowness,
actually - of matrix multiplication in Sage. The following is with
sage-4.7.1.rc1 plus the patches from #11589:
{{{
sage: MS = MatrixSpace(GF(64,'a'),5000,5000)
# I think the following is already WAY too slow!
sage: %time A = MS.random_element()
CPU times: user 38.42 s, sys: 0.13 s, total: 38.55 s
Wall time: 38.67 s
sage: B = MS.random_element()
sage: %time C = A*B
^C^C^C^C^C^C^C^C^C^C^C^C^C^C
}}}
In other words:
1. The computation can not be interrupted, which is a bug.
2. The computation takes more than 45 minutes!!!
3. The computation takes more than 880 MB.
As much as I see, GF(2) is the ''only'' finite field such that
multiplication of square matrices over that field is not blatantly slow in
Sage.
It makes me wonder if we shouldn't use a different package for matrix
multiplication over finite fields different from GF(2).
As much as I know, there already is an experimental version for matrices
over `GF(2^n)`, isn't it, Martin? How fast is it?
Over finite prime fields, we could use Linbox. There are tickets to do so.
But What about finite non-prime fields? Would it be a reasonable idea to
use something based on `MeatAxe`?
I will very likely be using a Sage wrapper for `MeatAxe` matrices in my
current project. So, I'll do the work anyway. From my perspective, the
only question is whether we can/should use it by default in Sage.
Here are some relevant data:
1. I work on top of `MeatAxe 2.2.4`. That version is identic with 2.2.3,
with one important difference. While all other meataxe versions are `GPL
2`, version 2.2.4 is `GPL 2+`. In fact, that version was made after I
wanted to use meataxe 2.2.3 in my group cohomology package and asked
Michael Ringe whether he could provide it in `GPL 2+`.
2. I am not just wrapping it, in fact I am branching meataxe. I improved
the implementation of the "school book" multiplication in meataxe, and I
implemented Strassen-Winograd multiplication, which had so far been
missing in meataxe.
3. It would provide a vastly better performance. The above 5000x5000
multiplication over GF(4) with the school book method needs 173.68 CPU
seconds and about 200 MB. With Strassen-Winograd, it is only 85.04 CPU
seconds, using less than 280 MB.
4. Concerning prime fields: A multiplication of two 5000x5000 matrices A,
B over GF(5) using `A._multipliy_linbox(B)` needs 21.49 CPU seconds and
1.2 GB(!). Using school book multiplication in meataxe, it is 46.70 s and
140 MB, or 30.29 CPU seconds and 160 MB using Strassen-Winograd.
__Conclusion__
* The licence of `MeatAxe 2.2.4` would be fine.
* The default matrix multiplication over finite fields that is currently
provided in Sage is not competitive at all.
* Over prime fields, Linbox is still faster, but my implementation of
Strassen multiplication needs only one tenth of the memory.
* As far as I know, Linbox does not officially support non-prime fields,
in contrast to meataxe. And Meataxe is a lot faster than the current
implementation in Sage, except for GF(2).
* My meataxe wrapper could still be improved - I have no idea of how to
optimize the use of L1 and L2 cache, and would need help to do so.
* Big disadvantage of my current meataxe wrapper: It only supports field
sizes less than 256. There is a "big" version of meataxe that can deal
with field sizes of up to `2^16-1`, but I did not wrap it yet, and I don't
know how difficult it would be.
As I said: I will work on that wrapper anyway, because it seems well
suited for my current project. But would it make sense in Sage as a
default implementation for matrices over small finite fields (or at least
over the non-prime fields)?
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8096#comment:18>
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.
