#8096: Speed up parent creation for multiplication of square matrices
------------------------------+---------------------------------------------
Reporter: boothby | Owner: boothby
Type: defect | Status: needs_review
Priority: minor | Milestone:
Component: linear algebra | Keywords:
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
------------------------------+---------------------------------------------
Comment(by SimonKing):
Replying to [comment:8 robertwb]:
> SimonKing: I'm impressed and depressed. Is MeatAxe's runtime a function
of the characteristic?
Yes. Over a non-prime field:
{{{
sage: F = GF(8,'t')
sage: A = random_matrix(F,2000)
sage: B = random_matrix(F,2000)
sage: from pGroupCohomology.mtx import MTX
sage: a = MTX(8,[list(r) for r in A.rows()])
sage: b = MTX(8,[list(r) for r in B.rows()])
sage: %time c = a*b
CPU times: user 5.19 s, sys: 0.00 s, total: 5.19 s
Wall time: 5.19 s
sage: %time C = A*B
}}}
The last line took several minutes, and it was not possible to interrupt
with Ctrl-c. So, I had to kill the Python process.
And with a bigger prime, comparing against linbox:
{{{
sage: F = GF(37)
sage: A = random_matrix(F,2000)
sage: B = random_matrix(F,2000)
sage: a = MTX(37,[list(r) for r in A.rows()])
sage: b = MTX(37,[list(r) for r in B.rows()])
sage: %time c = a*b
CPU times: user 11.83 s, sys: 0.00 s, total: 11.84 s
Wall time: 11.87 s
sage: %time C = A._multiply_linbox(B)
CPU times: user 1.82 s, sys: 0.00 s, total: 1.82 s
Wall time: 1.82 s
sage: %time C = A*B
CPU times: user 12.65 s, sys: 0.00 s, total: 12.65 s
Wall time: 12.70 s
}}}
In other words, for bigger fields, linbox is clearly better than !MeatAxe,
but the overhead kills it.
> At least one can do ` sage: A = random_matrix(GF(3), 2000) sage: B =
random_matrix(GF(3), 2000) sage: %timeit A._multiply_linbox(B) 5 loops,
best of 3: 1.9 s per loop`
Again, there is a huge overhead. But at what point? I mean, the parents of
A and B are the same, so, it can't be in the coercion model. And if two
matrices have the same parent, then I'd expect that `A*B` would simply
call A._multiply_linbox(B).
> Tom: Your patch looks good, positive review to that. I've posted another
patch which provides another 2x speedup. There's still a lot of cruft it
goes through, and matrix_space could really stand to be cythonized (there
are 3 mandatory Python calls on it every time a matrix is created), but I
don't have time to dig through it now.
Which means, a third person (e.g.) should review both Tom's and your
patch, right?
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8096#comment:9>
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.
