Sage: Ticket #10568: Multiplying sparse matrices by integers is unnecessarily slow
https://trac.sagemath.org/ticket/10568
<p>
The below shows that a speedup of a factor 20 or more can be obtained in certain cases
</p>
<pre class="wiki">sage: M=MatrixSpace(QQ,1240,3720,sparse=true)
sage: m=M.random_element(density=4/3720)
sage: time a=2*m
CPU times: user 8.17 s, sys: 0.02 s, total: 8.19 s
Wall time: 8.33 s
sage: time b=diagonal_matrix(QQ,1240,2,sparse=True)*m
CPU times: user 0.33 s, sys: 0.00 s, total: 0.33 s
Wall time: 0.34 s
sage: a==b
True
</pre>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/10568
Trac 1.1.6mderickxFri, 07 Jan 2011 16:55:31 GMT
https://trac.sagemath.org/ticket/10568#comment:1
https://trac.sagemath.org/ticket/10568#comment:1
<p>
it can be even faster then the second suggestion. with still the same m as above:
</p>
<p>
sage: time for key in m._dict(): m._dict()[key]=2*(m._dict()[key])
CPU times: user 0.03 s, sys: 0.00 s, total: 0.04 s
Wall time: 0.04 s
</p>
TicketmderickxFri, 07 Jan 2011 17:02:24 GMT
https://trac.sagemath.org/ticket/10568#comment:2
https://trac.sagemath.org/ticket/10568#comment:2
<p>
With the patch applied I now get:
</p>
<pre class="wiki">sage: M=MatrixSpace(QQ,1240,3720,sparse=true)
sage: m=M.random_element(density=4/3720)
sage: set_verbose(2)
sage: m._lmul_(2)
verbose 2 (_lmul_) scalar multiplying
verbose 2 (_lmul_) scalar multiplying finished (time = 0.033165)
1240 x 3720 sparse matrix over Rational Field (type 'print m.str()' to see all of the entries)
sage: time 2*m
CPU times: user 15.97 s, sys: 0.04 s, total: 16.01 s
Wall time: 16.36 s
1240 x 3720 sparse matrix over Rational Field
sage: time m*2
CPU times: user 15.93 s, sys: 0.04 s, total: 15.97 s
Wall time: 16.46 s
1240 x 3720 sparse matrix over Rational Field
</pre><p>
So the newer and faster _lmul_ is there but for some reason it is not called.
</p>
TicketmderickxFri, 07 Jan 2011 17:28:45 GMT
https://trac.sagemath.org/ticket/10568#comment:3
https://trac.sagemath.org/ticket/10568#comment:3
<p>
And its not because 2 is an integer and not a rational since the following also doesn't work:
</p>
<pre class="wiki">sage: M=MatrixSpace(QQ,1240,3720,sparse=true)
sage: m=M.random_element(density=4/3720)
sage: set_verbose(2)
sage: QQ(2)*m
</pre>
TicketmderickxTue, 11 Jan 2011 01:45:14 GMTattachment set
https://trac.sagemath.org/ticket/10568
https://trac.sagemath.org/ticket/10568
<ul>
<li><strong>attachment</strong>
set to <em>10553-DiamondBrackedSpeedup</em>
</li>
</ul>
TicketmderickxTue, 11 Jan 2011 01:45:40 GMTattachment set
https://trac.sagemath.org/ticket/10568
https://trac.sagemath.org/ticket/10568
<ul>
<li><strong>attachment</strong>
set to <em>10568-speedup-QQmatrix-lmul.2</em>
</li>
</ul>
TicketmderickxTue, 11 Jan 2011 01:53:48 GMTstatus changed
https://trac.sagemath.org/ticket/10568#comment:4
https://trac.sagemath.org/ticket/10568#comment:4
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
<p>
Ok the problem was that I had to cpdef the _lmul_ operator. It's now dramatically faster as the following shows:
</p>
<pre class="wiki">sage: M=MatrixSpace(QQ,1240,3720,sparse=true)
sage: m=M.random_element(density=4/3720)
sage: set_verbose(2)
sage: time QQ(2)*m
CPU times: user 0.03 s, sys: 0.00 s, total: 0.03 s
Wall time: 0.03 s
1240 x 3720 sparse matrix over Rational Field
</pre><p>
The old code was multiplying sparse matrices as if they were still regular (dense) matrices, so no wonder it was terribly slow.
</p>
TicketmderickxTue, 11 Jan 2011 01:54:41 GMT
https://trac.sagemath.org/ticket/10568#comment:5
https://trac.sagemath.org/ticket/10568#comment:5
<p>
By the way, I fail with uploading files. Only apply:
10568-speedup-QQmatrix-lmul
</p>
TicketmderickxTue, 11 Jan 2011 12:02:59 GMTattachment set
https://trac.sagemath.org/ticket/10568
https://trac.sagemath.org/ticket/10568
<ul>
<li><strong>attachment</strong>
set to <em>10568-speedup-QQmatrix-lmul</em>
</li>
</ul>
TicketrbeezerMon, 07 Feb 2011 21:49:53 GMTstatus changed; author set
https://trac.sagemath.org/ticket/10568#comment:6
https://trac.sagemath.org/ticket/10568#comment:6
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_info</em>
</li>
<li><strong>author</strong>
set to <em>Maarten Derickx</em>
</li>
</ul>
<p>
Maarten,
</p>
<p>
Looks real good and is a good thing to get into Sage. Seems like sparse matrices are often neglected. I bet there is more like this to be done in other places. I used just <code>10568-speedup-QQmatrix-lmul</code>, which I hope was the right file. Some comments and suggestions follow.
</p>
<p>
Rob
</p>
<ul><li>I like the HUGE doctest. ;-)
</li></ul><ul><li>A doctest like the following might be a nice addition - it'd show a multiplier outside the base ring cooperating with the coercion model and doing the right thing.
</li></ul><pre class="wiki">sage: F = FiniteField(3)
sage: two = F(2)
sage: A = matrix(ZZ, 3, range(30), sparse=True)
sage: B = two*A; B
[0 2 1 0 2 1 0 2 1 0]
[2 1 0 2 1 0 2 1 0 2]
[1 0 2 1 0 2 1 0 2 1]
sage: B.parent()
Full MatrixSpace of 3 by 10 sparse matrices over Finite Field of size 3
</pre><ul><li>How about an <code>INPUT:</code> and <code>OUTPUT:</code> block in the docstring? Even though these internal methods don't show in tab-completion, you can still view them in the notebook with formatting, so I think the consistent style is a good idea.
</li></ul><ul><li>If you name your files as <code>*.patch</code> then Trac gives a very nice red-green/leaving-entering view and my local patch viewer (kompare) will do tab-completion on the filename. ;-)
</li></ul><ul><li>I'd imagine the release manager can clear out the two uploads you didn't want?
</li></ul>
TicketmderickxTue, 08 Feb 2011 11:02:11 GMTstatus changed
https://trac.sagemath.org/ticket/10568#comment:7
https://trac.sagemath.org/ticket/10568#comment:7
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
</ul>
<p>
Yeah, I thought the HUGE doctest was nice to :). It at least shows what is different about this function compared to the function it overwrites. And it makes sure that if someone accidentally replaces this function by something not sparse that the doctest would never complete :).
</p>
<p>
I don't think the doctest you suggest is a good addition in this particular place, from the reference manual <a href="http://www.sagemath.org/doc/reference/coercion.html">http://www.sagemath.org/doc/reference/coercion.html</a>:
</p>
<pre class="wiki">If R is the base of S (as in the first example), simply implement
_rmul_ and/or _lmul_ on the Elements of S. In this case r * s gets
handled as s._rmul_(r) and s * r as s._lmul_(r). The argument to
_rmul_ and _lmul_ are guaranteed to be Elements of the base of S (with
coercion happening beforehand if necessary).
</pre><p>
So the new code has noting to do with coercion. I really think that tests should be performed in the place where the relevant code is. Since there is no coercion happening in this low level _lmul_ function this should not be tested here.
</p>
<p>
Input and output block are added and now with .patch extension :
</p>
TicketmderickxTue, 08 Feb 2011 11:14:11 GMTcc set
https://trac.sagemath.org/ticket/10568#comment:8
https://trac.sagemath.org/ticket/10568#comment:8
<ul>
<li><strong>cc</strong>
<em>rbeezer</em> added
</li>
</ul>
TicketrbeezerTue, 08 Feb 2011 18:22:28 GMTstatus changed; reviewer, milestone set; cc deleted
https://trac.sagemath.org/ticket/10568#comment:9
https://trac.sagemath.org/ticket/10568#comment:9
<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>
<li><strong>cc</strong>
<em>rbeezer</em> removed
</li>
<li><strong>milestone</strong>
set to <em>sage-4.6.2</em>
</li>
</ul>
<p>
Maarten,
</p>
<p>
I like my doctests to mash up as much of Sage as possible, and show how different things work together. But you have a good argument. And as an underscore method it's not that critical, anyway.
</p>
<p>
Trac Tip: once somebody comments on a ticket, they get email for life on that one, so no need to add such a person to the cc.
</p>
<p>
Passes all tests. Nice contribution!
</p>
<p>
Rob
</p>
TicketjdemeyerTue, 08 Feb 2011 21:04:37 GMTmilestone, summary changed
https://trac.sagemath.org/ticket/10568#comment:10
https://trac.sagemath.org/ticket/10568#comment:10
<ul>
<li><strong>milestone</strong>
changed from <em>sage-4.6.2</em> to <em>sage-4.7</em>
</li>
<li><strong>summary</strong>
changed from <em>multipying sparse matrices by integers in unnecceraly slow</em> to <em>Multiplying sparse matrices by integers is unnecessarily slow</em>
</li>
</ul>
TicketjdemeyerTue, 08 Mar 2011 10:40:45 GMTstatus changed
https://trac.sagemath.org/ticket/10568#comment:11
https://trac.sagemath.org/ticket/10568#comment:11
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
The patch seems not to be a proper HG changeset. Patches should be made using <code>hg export tip</code> (and not <code>hg diff</code>).
</p>
TicketmderickxTue, 08 Mar 2011 11:12:12 GMT
https://trac.sagemath.org/ticket/10568#comment:12
https://trac.sagemath.org/ticket/10568#comment:12
<p>
Sorry, jeroen. I thought uploading files from my .hg/patches/ was easier then having to create a patch again each time. But apparently the files are not stored there in a proper patch format. I uploaded a proper one now.
</p>
TicketmderickxTue, 08 Mar 2011 11:12:29 GMTstatus changed
https://trac.sagemath.org/ticket/10568#comment:13
https://trac.sagemath.org/ticket/10568#comment:13
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>positive_review</em>
</li>
</ul>
TicketjdemeyerTue, 08 Mar 2011 11:24:22 GMTstatus changed
https://trac.sagemath.org/ticket/10568#comment:14
https://trac.sagemath.org/ticket/10568#comment:14
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/10568#comment:12" title="Comment 12">mderickx</a>:
</p>
<blockquote class="citation">
<p>
Sorry, jeroen. I thought uploading files from my .hg/patches/ was easier then having to create a patch again each time. But apparently the files are not stored there in a proper patch format. I uploaded a proper one now.
</p>
</blockquote>
<p>
I think you did something wrong, because the "new" file is exactly the same as the old.
</p>
TicketmderickxTue, 08 Mar 2011 11:32:11 GMTattachment set
https://trac.sagemath.org/ticket/10568
https://trac.sagemath.org/ticket/10568
<ul>
<li><strong>attachment</strong>
set to <em>10568-speedup-QQmatrix-lmul.patch</em>
</li>
</ul>
<p>
Use this one, the others are old version
</p>
TicketmderickxTue, 08 Mar 2011 11:33:34 GMTstatus changed
https://trac.sagemath.org/ticket/10568#comment:15
https://trac.sagemath.org/ticket/10568#comment:15
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>positive_review</em>
</li>
</ul>
<p>
I must be the worst person ever with uploading patches. So here is the right one finally I hope.
</p>
TicketjdemeyerTue, 08 Mar 2011 21:46:10 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/10568#comment:16
https://trac.sagemath.org/ticket/10568#comment:16
<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.alpha1</em>
</li>
</ul>
Ticket