Sage: Ticket #10763: Speedup of matrix multiplication
https://trac.sagemath.org/ticket/10763
<p>
When multiplying two matrices M and N, typically one first creates a zero matrix of an appropriate matrix space. That means:
</p>
<ul><li>Call <code>M.matrix_space(...)</code>.
</li><li>This calls <code>M.parent().matrix_space(...)</code>.
</li><li>This calls <code>MatrixSpace(...)</code>.
</li><li>This tests, whether the base ring really is a ring and whether the matrix space is already in the cache.
</li></ul><p>
This can obviously be improved:
</p>
<ul><li><code>M.matrix_space(...)</code> should avoid the overhead of calling <code>M.parent()</code> but create the matrix space directly.
</li><li>It is already known that the base ring is a ring. So, there is no need to test it.
</li><li>One may access the cache directly, thus, avoid the overhead of calling <code>MatrixSpace</code>.
</li></ul><p>
I guess the ticket belongs to linear algebra. Correct me if I'm wrong.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/10763
Trac 1.1.6SimonKingWed, 09 Feb 2011 18:23:32 GMTstatus changed; author set
https://trac.sagemath.org/ticket/10763#comment:1
https://trac.sagemath.org/ticket/10763#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>author</strong>
set to <em>Simon King</em>
</li>
</ul>
<p>
I did not run the doc test yet, but I think it already ready for review.
</p>
<p>
Here are timings. Note that the reduced overhead is most visible when the multiplication itself is trivial.
</p>
<p>
Without the patch:
</p>
<pre class="wiki">sage: def test(M):
....: for i in xrange(10^6):
....: M*=M
....: return M
....:
sage: m = matrix(GF(3),[[1]])
sage: %time test(m)
CPU times: user 51.36 s, sys: 0.16 s, total: 51.52 s
Wall time: 51.67 s
[1]
sage: m = matrix(GF(2),[[1]])
sage: %time test(m)
CPU times: user 39.16 s, sys: 0.20 s, total: 39.36 s
Wall time: 39.47 s
[1]
sage: m = matrix(ZZ,[[1]])
# apparently there is no overhead for matrices over ZZ
sage: %time test(m)
CPU times: user 7.81 s, sys: 0.15 s, total: 7.96 s
Wall time: 7.99 s
[1]
</pre><p>
With the patch
</p>
<pre class="wiki">sage: def test(M):
....: for i in xrange(10^6):
....: M*=M
....: return M
....:
sage: m = matrix(GF(3),[[1]])
sage: %time test(m)
CPU times: user 33.65 s, sys: 0.30 s, total: 33.95 s
Wall time: 34.05 s
[1]
sage: m = matrix(GF(2),[[1]])
sage: %time test(m)
CPU times: user 25.41 s, sys: 0.10 s, total: 25.51 s
Wall time: 25.58 s
[1]
sage: m = matrix(ZZ,[[1]])
sage: %time test(m)
CPU times: user 7.62 s, sys: 0.16 s, total: 7.78 s
Wall time: 7.80 s
[1]
</pre><p>
Thus, over <code>GF(3)</code> and <code>GF(2)</code> the overhead is clearly reduced.
</p>
<p>
I don't know how the patch could be doc-tested, as it only concerns the performance.
</p>
TicketSimonKingThu, 10 Feb 2011 08:59:49 GMTstatus changed
https://trac.sagemath.org/ticket/10763#comment:2
https://trac.sagemath.org/ticket/10763#comment:2
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Apparently the small change led to some problems. So, it needs work.
</p>
TicketSimonKingThu, 10 Feb 2011 09:18:30 GMTstatus changed
https://trac.sagemath.org/ticket/10763#comment:3
https://trac.sagemath.org/ticket/10763#comment:3
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
The problem was that the matrix spaces are cached with weak references. It could happen that the key was still available, but <code>_cache[key]</code> was a reference to <code>None</code>. So, in the updated patch I am not simply trying to return <code>_cache[key]()</code> but I first test if it is not None.
</p>
<p>
Back to "needs review"...
</p>
TicketSimonKingThu, 10 Feb 2011 09:21:18 GMT
https://trac.sagemath.org/ticket/10763#comment:4
https://trac.sagemath.org/ticket/10763#comment:4
<p>
PS:
</p>
<p>
The timings with the new patch are
</p>
<pre class="wiki">sage: def test(M):
....: for i in xrange(10^6):
....: M*=M
....: return M
....:
sage: m = matrix(GF(3),[[1]])
sage: %time test(m)
CPU times: user 37.70 s, sys: 0.18 s, total: 37.89 s
Wall time: 38.00 s
[1]
sage: m = matrix(GF(2),[[1]])
sage: %time test(m)
CPU times: user 27.09 s, sys: 0.17 s, total: 27.26 s
Wall time: 27.34 s
[1]
</pre><p>
That's still a lot faster than without patch.
</p>
TicketSimonKingFri, 11 Feb 2011 07:33:43 GMT
https://trac.sagemath.org/ticket/10763#comment:5
https://trac.sagemath.org/ticket/10763#comment:5
<p>
I updated the patch, so that it cleanly applies to <code>sage-4.6.2.alpha4</code>.
</p>
TicketrbeezerTue, 15 Feb 2011 05:03:39 GMT
https://trac.sagemath.org/ticket/10763#comment:6
https://trac.sagemath.org/ticket/10763#comment:6
<p>
I ran tests in sage/matrix and got failures in matrix_mod2_dense.pyx and matrix2.pyx. Mostly complaints about improper dimensions it seems. The mod2 code appears to have some internal checks that are triggered even before the test itself fails.
</p>
TicketSimonKingTue, 15 Feb 2011 07:25:56 GMTstatus changed
https://trac.sagemath.org/ticket/10763#comment:7
https://trac.sagemath.org/ticket/10763#comment:7
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/10763#comment:6" title="Comment 6">rbeezer</a>:
</p>
<blockquote class="citation">
<p>
I ran tests in sage/matrix and got failures in matrix_mod2_dense.pyx and matrix2.pyx. Mostly complaints about improper dimensions it seems. The mod2 code appears to have some internal checks that are triggered even before the test itself fails.
</p>
</blockquote>
<p>
Thank you! As I wrote when I posted my patch, I hadn't run the tests, and then I was working on different tickets. Now I'll try to hunt it down.
</p>
TicketSimonKingTue, 15 Feb 2011 07:52:35 GMTstatus changed
https://trac.sagemath.org/ticket/10763#comment:8
https://trac.sagemath.org/ticket/10763#comment:8
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
The test failures were caused by a very stupid mistake: <code>self.new_matrix()</code> by default assumes that the dimension of the new matrix is the same as the dimension of the old matrix. In the multiplication algorithms, I saw <code>self.new_matrix(nrows=self.nrows(),...)</code>, was not reading further, and thought that we are in the default case, thus, deleted the arguments.
</p>
<p>
Of course, it continues "(..., ncols=right.ncols())`.
</p>
<p>
What I did now was to avoid calling <code>self.nrows()</code> and <code>right.ncols()</code> - direct access to the attributes <code>self._nrows</code> and <code>right._ncols</code> is faster.
</p>
<p>
To my surprise, the timings improved a little more:
</p>
<pre class="wiki">sage: def test(M):
....: for i in xrange(10^6):
....: M*=M
....: return M
....:
sage: m = matrix(GF(3),[[1]])
sage: %time test(m)
CPU times: user 36.67 s, sys: 0.16 s, total: 36.83 s
Wall time: 36.95 s
[1]
sage: m = matrix(GF(2),[[1]])
sage: %time test(m)
CPU times: user 26.29 s, sys: 0.14 s, total: 26.43 s
Wall time: 26.50 s
[1]
</pre><p>
Is it faster to provide arguments with a default value <em>explicitly</em>?
</p>
<p>
The tests for <code>sage/matrix/</code> passed. I am now running all doctests (not the long ones), but I think I can already revert it to "needs review".
</p>
TicketSimonKingWed, 16 Feb 2011 10:22:35 GMT
https://trac.sagemath.org/ticket/10763#comment:9
https://trac.sagemath.org/ticket/10763#comment:9
<p>
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.
</p>
<p>
<strong><span class="underline">Updated timings in sage.4.6.2.alpha4</span></strong>
</p>
<pre class="wiki">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])
</pre><p>
Without patch:
</p>
<pre class="wiki">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]
</pre><p>
With patch:
</p>
<pre class="wiki">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]
</pre><p>
Or, with the (dense) examples that I used in the previous posts:
</p>
<pre class="wiki">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]
</pre><p>
So, the progress is clear.
</p>
<p>
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".
</p>
TicketSimonKingWed, 16 Feb 2011 12:56:08 GMT
https://trac.sagemath.org/ticket/10763#comment:10
https://trac.sagemath.org/ticket/10763#comment:10
<p>
PS: Long tests in devel/sage/sage and devel/sage/doc pass without error. The error that the patchbot reports is the usual error in startup.py and seems independent of my patch.
</p>
TicketrbeezerMon, 21 Feb 2011 20:56:45 GMTstatus changed
https://trac.sagemath.org/ticket/10763#comment:11
https://trac.sagemath.org/ticket/10763#comment:11
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_info</em>
</li>
</ul>
<p>
Simon,
</p>
<p>
Looks real good. One suggestion - and it really is <em>just</em> a suggestion. Your call.
</p>
<p>
Two instances of basically:
</p>
<pre class="wiki">try:
from sage.matrix.matrix_space import _cache
MS = _cache[base_ring, nrows, ncols, sparse]()
except KeyError:
return MatrixSpace(base_ring, nrows, ncols, sparse)
if MS is not None:
return MS
return MatrixSpace(base_ring, nrows, ncols, sparse)
</pre><p>
and a suggested replacement:
</p>
<pre class="wiki">try:
from sage.matrix.matrix_space import _cache
MS = _cache[base_ring, nrows, ncols, sparse]()
except KeyError:
MS = None
if MS is None:
return MatrixSpace(base_ring, nrows, ncols, sparse)
else:
return MS
</pre><p>
Suggestion uses try/except to form "best guess" for <code>MS</code>. Either we find it, or we get <code>None</code>. Then if/else returns it, or creates it and returns it.
</p>
<p>
An extra line, an extra comparison in one case, but the <code>not</code> is gone and most importantly, just one place to describe the actual <code>MatrixSpace</code> call (instead of two that are identical). Anyway, a toss-up, I'd guess, so just a suggestion.
</p>
<p>
In the meantime, I am going to run the full test suite right now.
</p>
<p>
Rob
</p>
TicketrbeezerTue, 22 Feb 2011 01:37:18 GMT
https://trac.sagemath.org/ticket/10763#comment:12
https://trac.sagemath.org/ticket/10763#comment:12
<p>
Passed all long tests. So, other than my suggestion above, this looks ready to go.
</p>
TicketSimonKingSat, 26 Feb 2011 13:21:01 GMTstatus changed
https://trac.sagemath.org/ticket/10763#comment:13
https://trac.sagemath.org/ticket/10763#comment:13
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/10763#comment:12" title="Comment 12">rbeezer</a>:
</p>
<blockquote class="citation">
<p>
Passed all long tests. So, other than my suggestion above, this looks ready to go.
</p>
</blockquote>
<p>
Can you turn your suggestion into a referee patch? I wouldn't object to the change.
</p>
<p>
Cheers,
</p>
<p>
Simon
</p>
TicketrbeezerSun, 27 Feb 2011 17:19:53 GMTattachment set
https://trac.sagemath.org/ticket/10763
https://trac.sagemath.org/ticket/10763
<ul>
<li><strong>attachment</strong>
set to <em>trac_10763-speedup-matrix-multiplication-reviewer.patch</em>
</li>
</ul>
TicketrbeezerSun, 27 Feb 2011 17:22:13 GMT
https://trac.sagemath.org/ticket/10763#comment:14
https://trac.sagemath.org/ticket/10763#comment:14
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/10763#comment:13" title="Comment 13">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Can you turn your suggestion into a referee patch? I wouldn't object to the change.
</p>
</blockquote>
<p>
Done and attached. Passes all long tests with the change. When you are satisfied with my changes, go ahead and flip this to "positive review" - everything looks good on my end.
</p>
<p>
Thanks for the speed increase!
</p>
<p>
Rob
</p>
TicketSimonKingSun, 27 Feb 2011 18:09:23 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/10763#comment:15
https://trac.sagemath.org/ticket/10763#comment:15
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Rob Beezer</em>
</li>
</ul>
<p>
Hi Rob,
</p>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/10763#comment:14" title="Comment 14">rbeezer</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/10763#comment:13" title="Comment 13">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Can you turn your suggestion into a referee patch? I wouldn't object to the change.
</p>
</blockquote>
<p>
Done and attached. Passes all long tests with the change. When you are satisfied with my changes, go ahead and flip this to "positive review"
</p>
</blockquote>
<p>
Done, adding your name in the "Reviewer" field.
</p>
<blockquote class="citation">
<p>
Thanks for the speed increase!
</p>
</blockquote>
<p>
You're welcome! After all, the speed increase was in my own interest.
</p>
<p>
Cheers,
</p>
<p>
Simon
</p>
TicketjdemeyerMon, 28 Feb 2011 08:42:16 GMTmilestone changed
https://trac.sagemath.org/ticket/10763#comment:16
https://trac.sagemath.org/ticket/10763#comment:16
<ul>
<li><strong>milestone</strong>
changed from <em>sage-4.6.2</em> to <em>sage-4.7</em>
</li>
</ul>
TicketjdemeyerWed, 16 Mar 2011 11:31:35 GMTstatus changed
https://trac.sagemath.org/ticket/10763#comment:17
https://trac.sagemath.org/ticket/10763#comment:17
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
The commit message of the patch should be broken up in multiple lines instead of one long line. The first line should stand by itself and must mention the ticket number, a more detailed message can come on following lines. Use <code>hg qrefresh -e</code> to change the commit message.
</p>
TicketSimonKingWed, 16 Mar 2011 11:48:02 GMTattachment set
https://trac.sagemath.org/ticket/10763
https://trac.sagemath.org/ticket/10763
<ul>
<li><strong>attachment</strong>
set to <em>trac10763-speedup_matrix_multiplication.patch</em>
</li>
</ul>
<p>
Improve performance of matrix multiplication by using a shortpath to matrix spaces and a shortpath in multiplication algorithms for creating a zero matrix
</p>
TicketSimonKingWed, 16 Mar 2011 11:50:57 GMTstatus changed
https://trac.sagemath.org/ticket/10763#comment:18
https://trac.sagemath.org/ticket/10763#comment:18
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>positive_review</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/10763#comment:17" title="Comment 17">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
The commit message of the patch should be broken up in multiple lines instead of one long line. The first line should stand by itself and must mention the ticket number, a more detailed message can come on following lines. Use <code>hg qrefresh -e</code> to change the commit message.
</p>
</blockquote>
<p>
Both patches <em>did</em> mention the ticket number, and I think it is questionable whether the message of my original patch was to long. Anyway, I just replaced it, and I hope you'll find that it is fine.
</p>
TicketjdemeyerWed, 16 Mar 2011 18:47:01 GMT
https://trac.sagemath.org/ticket/10763#comment:19
https://trac.sagemath.org/ticket/10763#comment:19
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/10763#comment:18" title="Comment 18">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
I think it is questionable whether the message of my original patch was to long.
</p>
</blockquote>
<p>
Just to clarify: the message itself was <em>not</em> too long, the problem was that the whole message was one long line without newlines. It should be wrapped to multiple lines instead (as you did in this case).
</p>
TicketjdemeyerThu, 17 Mar 2011 19:23:17 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/10763#comment:20
https://trac.sagemath.org/ticket/10763#comment:20
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-4.7.alpha2</em>
</li>
</ul>
Ticket