id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
20470 Conversion of sparse to dense matrices over F2 is unspeakably slow kedlaya "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
}}}" defect closed major sage-7.2 linear algebra fixed sparse matrices, dense matrices John Palmieri Kiran Kedlaya N/A 2cacd0e2eac07fbbe2d8a30496cc8c5c11e0a4b4 2cacd0e2eac07fbbe2d8a30496cc8c5c11e0a4b4