Opened 5 years ago
Closed 5 years ago
#20470 closed defect (fixed)
Conversion of sparse to dense matrices over F2 is unspeakably slow
Reported by:  kedlaya  Owned by:  

Priority:  major  Milestone:  sage7.2 
Component:  linear algebra  Keywords:  sparse matrices, dense matrices 
Cc:  Merged in:  
Authors:  John Palmieri  Reviewers:  Kiran Kedlaya 
Report Upstream:  N/A  Work issues:  
Branch:  2cacd0e (Commits, GitHub, GitLab)  Commit:  2cacd0e2eac07fbbe2d8a30496cc8c5c11e0a4b4 
Dependencies:  Stopgaps: 
Description
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:
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
Presumably this is an artifact of the constructor, as internal operations are much faster:
sage: time sT2F2a.rank() CPU times: user 14.4 s, sys: 63 ms, total: 14.5 s Wall time: 14.5 s 38098
By contrast, staying in the sparse realm has a price which I think is at most only partly related (see https://groups.google.com/forum/#!topic/sagedevel/l1O82XMC0zo for another contributing factor):
sage: time sT2F2.rank() CPU times: user 24min 54s, sys: 544 ms, total: 24min 55s Wall time: 24min 56s 38098
Change History (12)
comment:1 followup: ↓ 2 Changed 5 years ago by
comment:2 in reply to: ↑ 1 Changed 5 years ago by
Replying to jhpalmieri:
How much time does
time sT2F2a = sT2F2.dense_matrix()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
M2( sparse_matrix )
by calling thedense_matrix()
method, under suitable circumstances.)
That is indeed much faster:
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
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 dense_matrix()
method.
comment:3 Changed 5 years ago by
I think the culprit is the matrix
method for the MatrixSpace
class: when you do M2(...)
, it runs the __call__
method, which does this:
return self.matrix(entries, coerce, copy)
Then the matrix
method does this, if the input x
is a matrix with the right size:
x = x.list() # this is the slow part ... x = list_to_dict(x, m, n)
So it should instead call dense_matrix
.
comment:4 Changed 5 years ago by
 Branch set to u/jhpalmieri/densesparse
comment:5 Changed 5 years ago by
 Commit set to 1cdcf1e9eac2ab4c5a8f5a2275a59110ca2db865
 Status changed from new to needs_review
New commits:
1cdcf1e  trac 20470: speed up MatrixSpace.__call__ when converting sparse to dense.

comment:6 Changed 5 years ago by
Patchbot throws up a weird error but I can't tell whether it's meaningful.
More seriously, is there a good way to doctest this?
comment:7 Changed 5 years ago by
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.
comment:8 Changed 5 years ago by
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).
comment:9 Changed 5 years ago by
 Commit changed from 1cdcf1e9eac2ab4c5a8f5a2275a59110ca2db865 to 2cacd0e2eac07fbbe2d8a30496cc8c5c11e0a4b4
Branch pushed to git repo; I updated commit sha1. New commits:
2cacd0e  trac 20470: add a doctest

comment:10 Changed 5 years ago by
Okay, good idea, here is a doctest.
comment:11 Changed 5 years ago by
 Reviewers set to Kiran Kedlaya
 Status changed from needs_review to positive_review
I'm not sure what the deal is with patchbot, but on my machine this passes all doctests. Positive review.
comment:12 Changed 5 years ago by
 Branch changed from u/jhpalmieri/densesparse to 2cacd0e2eac07fbbe2d8a30496cc8c5c11e0a4b4
 Resolution set to fixed
 Status changed from positive_review to closed
How much time does
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
M2( sparse_matrix )
by calling thedense_matrix()
method, under suitable circumstances.)