Opened 6 years ago

Closed 6 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: sage-7.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:

Status badges

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/sage-devel/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 follow-up: Changed 6 years ago by 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 the dense_matrix() method, under suitable circumstances.)

comment:2 in reply to: ↑ 1 Changed 6 years ago by kedlaya

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 the dense_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 6 years ago by jhpalmieri

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 6 years ago by jhpalmieri

  • Branch set to u/jhpalmieri/dense-sparse

comment:5 Changed 6 years ago by jhpalmieri

  • Authors set to John Palmieri
  • Commit set to 1cdcf1e9eac2ab4c5a8f5a2275a59110ca2db865
  • Status changed from new to needs_review

New commits:

1cdcf1etrac 20470: speed up MatrixSpace.__call__ when converting sparse to dense.

comment:6 Changed 6 years ago by kedlaya

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 6 years ago by jhpalmieri

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 6 years ago by tscrim

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 6 years ago by git

  • Commit changed from 1cdcf1e9eac2ab4c5a8f5a2275a59110ca2db865 to 2cacd0e2eac07fbbe2d8a30496cc8c5c11e0a4b4

Branch pushed to git repo; I updated commit sha1. New commits:

2cacd0etrac 20470: add a doctest

comment:10 Changed 6 years ago by jhpalmieri

Okay, good idea, here is a doctest.

comment:11 Changed 6 years ago by kedlaya

  • 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 6 years ago by vbraun

  • Branch changed from u/jhpalmieri/dense-sparse to 2cacd0e2eac07fbbe2d8a30496cc8c5c11e0a4b4
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.