#10763: Speedup of matrix multiplication
------------------------------+---------------------------------------------
Reporter: SimonKing | Owner: jason, was
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-4.6.2
Component: linear algebra | Keywords: matrix multiplication
Author: Simon King | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
------------------------------+---------------------------------------------
Comment(by SimonKing):
I was updating the patch again. I am now also taking more care of sparse
matrices, and I found yet another spot where overhead by calling methods
could be reduced.
'''__Updated timings in sage.4.6.2.alpha4__'''
{{{
sage: def test(M):
....: for i in xrange(10^6):
....: M*=M
....: return M
....:
sage: MS = MatrixSpace(GF(5),5,5,sparse=True)
sage: ms = MS([3, 1, 0, 0, 4, 1, 2, 2, 3, 4, 2, 4, 1, 0, 3, 4, 3, 1, 2, 4,
0, 0, 0, 1, 3])
sage: MD = MatrixSpace(GF(5),5,5,sparse=False)
sage: md = MD([3, 1, 0, 0, 4, 1, 2, 2, 3, 4, 2, 4, 1, 0, 3, 4, 3, 1, 2, 4,
0, 0, 0, 1, 3])
}}}
Without patch:
{{{
sage: %time test(ms)
CPU times: user 42.41 s, sys: 0.01 s, total: 42.43 s
Wall time: 42.57 s
[1 2 4 4 3]
[3 1 2 1 3]
[1 2 2 3 1]
[2 4 0 4 4]
[2 4 2 1 3]
sage: %time test(md)
CPU times: user 53.54 s, sys: 0.20 s, total: 53.74 s
Wall time: 53.90 s
[1 2 4 4 3]
[3 1 2 1 3]
[1 2 2 3 1]
[2 4 0 4 4]
[2 4 2 1 3]
}}}
With patch:
{{{
sage: %time test(ms)
CPU times: user 29.72 s, sys: 0.03 s, total: 29.75 s
Wall time: 29.84 s
[1 2 4 4 3]
[3 1 2 1 3]
[1 2 2 3 1]
[2 4 0 4 4]
[2 4 2 1 3]
sage: %time test(md)
CPU times: user 34.13 s, sys: 0.36 s, total: 34.49 s
Wall time: 34.59 s
[1 2 4 4 3]
[3 1 2 1 3]
[1 2 2 3 1]
[2 4 0 4 4]
[2 4 2 1 3]
}}}
Or, with the (dense) examples that I used in the previous posts:
{{{
sage: m = matrix(GF(2),[[1]])
sage: %time test(m)
CPU times: user 22.87 s, sys: 0.12 s, total: 22.99 s
Wall time: 23.06 s
[1]
sage: m = matrix(GF(3),[[1]])
sage: %time test(m)
CPU times: user 33.31 s, sys: 0.12 s, total: 33.43 s
Wall time: 33.52 s
[1]
}}}
So, the progress is clear.
I am now running doc tests (there was no problem for the previous patch),
but I think it is safe to keep it "needs review".
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10763#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.
