#20470: Conversion of sparse to dense matrices over F2 is unspeakably slow
-------------------------+-------------------------------------------------
Reporter: kedlaya | Owner:
Type: defect | Status: new
Priority: major | Milestone: sage-7.2
Component: linear | Keywords: sparse matrices, dense
algebra | matrices
Merged in: | Authors:
Reviewers: | Report Upstream: N/A
Work issues: | Branch:
Commit: | Dependencies:
Stopgaps: |
-------------------------+-------------------------------------------------
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
}}}
--
Ticket URL: <http://trac.sagemath.org/ticket/20470>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
