Sage: Ticket #20470: Conversion of sparse to dense matrices over F2 is unspeakably slow
https://trac.sagemath.org/ticket/20470
<p>
Converting a sparse matrix to a dense one should be an easy operation: create the zero matrix and then populate a few entries. But behold:
</p>
<pre class="wiki">sage: time S = CremonaModularSymbols(400001, sign=+1)
CPU times: user 15 s, sys: 36 ms, total: 15 s
Wall time: 15 s
sage: time T2 = S.hecke_matrix(2) # This matrix has <= 3 nonzero entries per row
CPU times: user 11.6 s, sys: 4.19 s, total: 15.8 s
Wall time: 15.8 s
sage: time sT2 = T2.sage_matrix_over_ZZ()
CPU times: user 1.56 s, sys: 1e+03 µs, total: 1.56 s
Wall time: 1.56 s
sage: time sT2F2 = sT2.change_ring(GF(2))
sage: time sT2F2 = sT2.change_ring(GF(2))
CPU times: user 979 ms, sys: 8 ms, total: 987 ms
Wall time: 987 ms
sage: sT2F2
38098 x 38098 sparse matrix over Finite Field of size 2 (use the '.str()' method to see the entries)
sage: M2 = MatrixSpace(GF(2), 38098, sparse=False)
sage: time sT2F2a = M2(sT2F2) #unspeakably slow!
CPU times: user 19min 43s, sys: 47.2 s, total: 20min 30s
Wall time: 20min 31s
</pre><p>
Presumably this is an artifact of the constructor, as internal operations are much faster:
</p>
<pre class="wiki">sage: time sT2F2a.rank()
CPU times: user 14.4 s, sys: 63 ms, total: 14.5 s
Wall time: 14.5 s
38098
</pre><p>
By contrast, staying in the sparse realm has a price which I think is at most only partly related (see <a class="ext-link" href="https://groups.google.com/forum/#!topic/sage-devel/l1O82XMC0zo"><span class="icon"></span>https://groups.google.com/forum/#!topic/sage-devel/l1O82XMC0zo</a> for another contributing factor):
</p>
<pre class="wiki">sage: time sT2F2.rank()
CPU times: user 24min 54s, sys: 544 ms, total: 24min 55s
Wall time: 24min 56s
38098
</pre>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/20470
Trac 1.1.6jhpalmieriTue, 19 Apr 2016 20:50:55 GMT
https://trac.sagemath.org/ticket/20470#comment:1
https://trac.sagemath.org/ticket/20470#comment:1
<p>
How much time does
</p>
<pre class="wiki">time sT2F2a = sT2F2.dense_matrix()
</pre><p>
take? I tried with a smaller matrix, and it's much faster than plugging the matrix into the appropriate matrix space. (That doesn't mean that there isn't a problem, rather that someone could possibly speed up <code>M2( sparse_matrix )</code> by calling the <code>dense_matrix()</code> method, under suitable circumstances.)
</p>
TicketkedlayaTue, 19 Apr 2016 20:56:05 GMT
https://trac.sagemath.org/ticket/20470#comment:2
https://trac.sagemath.org/ticket/20470#comment:2
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/20470#comment:1" title="Comment 1">jhpalmieri</a>:
</p>
<blockquote class="citation">
<p>
How much time does
</p>
<pre class="wiki">time sT2F2a = sT2F2.dense_matrix()
</pre><p>
take? I tried with a smaller matrix, and it's much faster than plugging the matrix into the appropriate matrix space. (That doesn't mean that there isn't a problem, rather that someone could possibly speed up <code>M2( sparse_matrix )</code> by calling the <code>dense_matrix()</code> method, under suitable circumstances.)
</p>
</blockquote>
<p>
That is indeed much faster:
</p>
<pre class="wiki">sage: time sT2F2b = sT2F2.dense_matrix()
CPU times: user 318 ms, sys: 47 ms, total: 365 ms
Wall time: 365 ms
sage: sT2F2a == sT2F2b
True
</pre><p>
I guess that means this is easy to fix: the constructor for dense matrices (over any base), upon receiving a sparse matrix as input, should simply call the <code>dense_matrix()</code> method.
</p>
TicketjhpalmieriTue, 19 Apr 2016 23:05:35 GMT
https://trac.sagemath.org/ticket/20470#comment:3
https://trac.sagemath.org/ticket/20470#comment:3
<p>
I think the culprit is the <code>matrix</code> method for the <code>MatrixSpace</code> class: when you do <code>M2(...)</code>, it runs the <code>__call__</code> method, which does this:
</p>
<pre class="wiki"> return self.matrix(entries, coerce, copy)
</pre><p>
Then the <code>matrix</code> method does this, if the input <code>x</code> is a matrix with the right size:
</p>
<pre class="wiki">x = x.list() # this is the slow part
...
x = list_to_dict(x, m, n)
</pre><p>
So it should instead call <code>dense_matrix</code>.
</p>
TicketjhpalmieriTue, 19 Apr 2016 23:05:56 GMTbranch set
https://trac.sagemath.org/ticket/20470#comment:4
https://trac.sagemath.org/ticket/20470#comment:4
<ul>
<li><strong>branch</strong>
set to <em>u/jhpalmieri/dense-sparse</em>
</li>
</ul>
TicketjhpalmieriTue, 19 Apr 2016 23:06:40 GMTstatus changed; commit, author set
https://trac.sagemath.org/ticket/20470#comment:5
https://trac.sagemath.org/ticket/20470#comment:5
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
set to <em>1cdcf1e9eac2ab4c5a8f5a2275a59110ca2db865</em>
</li>
<li><strong>author</strong>
set to <em>John Palmieri</em>
</li>
</ul>
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=1cdcf1e9eac2ab4c5a8f5a2275a59110ca2db865"><span class="icon"></span>1cdcf1e</a></td><td><code>trac 20470: speed up MatrixSpace.__call__ when converting sparse to dense.</code>
</td></tr></table>
TicketkedlayaWed, 20 Apr 2016 00:19:39 GMT
https://trac.sagemath.org/ticket/20470#comment:6
https://trac.sagemath.org/ticket/20470#comment:6
<p>
Patchbot throws up a weird error but I can't tell whether it's meaningful.
</p>
<p>
More seriously, is there a good way to doctest this?
</p>
TicketjhpalmieriWed, 20 Apr 2016 02:53:21 GMT
https://trac.sagemath.org/ticket/20470#comment:7
https://trac.sagemath.org/ticket/20470#comment:7
<p>
I think I've seen those patchbot errors on other tickets. I don't think they are related. Also, I thought about doctests, but since this is supposed to be a speed upgrade which does not change functionality, I couldn't come up with anything.
</p>
TickettscrimWed, 20 Apr 2016 04:29:17 GMT
https://trac.sagemath.org/ticket/20470#comment:8
https://trac.sagemath.org/ticket/20470#comment:8
<p>
You could add a doctest that took a long time prior (e.g., a few seconds) but now is quite quick (less than half a second).
</p>
TicketgitWed, 20 Apr 2016 15:19:40 GMTcommit changed
https://trac.sagemath.org/ticket/20470#comment:9
https://trac.sagemath.org/ticket/20470#comment:9
<ul>
<li><strong>commit</strong>
changed from <em>1cdcf1e9eac2ab4c5a8f5a2275a59110ca2db865</em> to <em>2cacd0e2eac07fbbe2d8a30496cc8c5c11e0a4b4</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=2cacd0e2eac07fbbe2d8a30496cc8c5c11e0a4b4"><span class="icon"></span>2cacd0e</a></td><td><code>trac 20470: add a doctest</code>
</td></tr></table>
TicketjhpalmieriWed, 20 Apr 2016 15:36:07 GMT
https://trac.sagemath.org/ticket/20470#comment:10
https://trac.sagemath.org/ticket/20470#comment:10
<p>
Okay, good idea, here is a doctest.
</p>
TicketkedlayaWed, 20 Apr 2016 18:13:53 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/20470#comment:11
https://trac.sagemath.org/ticket/20470#comment:11
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Kiran Kedlaya</em>
</li>
</ul>
<p>
I'm not sure what the deal is with patchbot, but on my machine this passes all doctests. Positive review.
</p>
TicketvbraunFri, 22 Apr 2016 07:13:02 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/20470#comment:12
https://trac.sagemath.org/ticket/20470#comment:12
<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>branch</strong>
changed from <em>u/jhpalmieri/dense-sparse</em> to <em>2cacd0e2eac07fbbe2d8a30496cc8c5c11e0a4b4</em>
</li>
</ul>
Ticket