Opened 7 years ago
Closed 2 years ago
#18312 closed defect (fixed)
Construction of a sparse matrix from sparse vectors does not exploit sparseness
Reported by:  nthiery  Owned by:  

Priority:  major  Milestone:  sage8.9 
Component:  linear algebra  Keywords:  sparse matrix constructor 
Cc:  jdemeyer, vdelecroix  Merged in:  
Authors:  Travis Scrimshaw  Reviewers:  Vincent Delecroix 
Report Upstream:  N/A  Work issues:  
Branch:  2044e52 (Commits, GitHub, GitLab)  Commit:  2044e5259d0b897c0b65d430c3c06f4a5444561a 
Dependencies:  Stopgaps: 
Description (last modified by )
sage: n = 10^3 sage: F = FreeModule(QQ, n, sparse=True) sage: v = F.an_element() sage: vectors = [v]*n sage: %time a = matrix(vectors, sparse=True) CPU times: user 2.01 s, sys: 38.4 ms, total: 2.05 s Wall time: 1.96 s
Compare with the construction of the same matrix through an intermediate dictionary:
sage: %time b = matrix(QQ, n, {(i,j): c for i,v in enumerate(vectors) for j,c in v.iteritems()}, sparse=True) CPU times: user 7.33 ms, sys: 124 µs, total: 7.46 ms Wall time: 6.06 ms sage: a == b True
Running %prun
shows that the input vectors are converted to dense
lists and back (gasp!), which gives a complexity of n^2
instead of
linear in the number of nonzero entries as would be expected.
See also: #10312
Change History (14)
comment:1 Changed 7 years ago by
 Description modified (diff)
 Keywords sparse matrix constructor added
comment:2 Changed 4 years ago by
 Branch set to public/linear_algebra/sparse_matrix_from_sparse_vectors18312
 Cc jdemeyer vdelecroix added
 Commit set to 5a1fe385e9843ac1a4fde84075cb78d172d3e29e
 Milestone changed from sage6.7 to sage8.1
 Status changed from new to needs_review
comment:3 Changed 4 years ago by
 Commit changed from 5a1fe385e9843ac1a4fde84075cb78d172d3e29e to dff2da179d6042e6633bfa5d0dc09269b45158db
Branch pushed to git repo; I updated commit sha1. New commits:
dff2da1  Merge branch 'public/linear_algebra/sparse_matrix_from_sparse_vectors18312' of git://trac.sagemath.org/sage into public/linear_algebra/sparse_matrix_from_sparse_vectors18312

comment:4 Changed 4 years ago by
 Milestone changed from sage8.1 to sage8.2
comment:5 Changed 3 years ago by
 Milestone changed from sage8.2 to sage8.3
 Status changed from needs_review to needs_work
 Work issues set to merge in develop
comment:6 Changed 3 years ago by
 Milestone changed from sage8.3 to sage8.4
update milestone 8.3 > 8.4
comment:7 Changed 2 years ago by
 Commit changed from dff2da179d6042e6633bfa5d0dc09269b45158db to c426c0c734bdb614c18b1a047dbe36e1d24bf86e
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
c426c0c  Extended MatrixArgs to special case list of vectors when sparse.

comment:8 Changed 2 years ago by
 Commit changed from c426c0c734bdb614c18b1a047dbe36e1d24bf86e to 2044e5259d0b897c0b65d430c3c06f4a5444561a
Branch pushed to git repo; I updated commit sha1. New commits:
2044e52  Fixing a bug with rank.

comment:9 Changed 2 years ago by
 Milestone changed from sage8.4 to sage8.9
 Status changed from needs_work to needs_review
 Work issues merge in develop deleted
Rebased on the matrix constructor and tests pass in the matrix folder.
comment:10 Changed 2 years ago by
In
if isinstance(e[0], Vector) and all(vec.is_sparse() for vec in e):
you seem to assume that if the first element of the list is a vector than all elements are. This would break on something like
matrix(3, [vector([0,1,0],sparse=True), [0,1,0], [1,1,1]])
comment:11 Changed 2 years ago by
I know, but that matches what sequence_type()
does. So I am just following the same assumption.
comment:12 Changed 2 years ago by
 Reviewers set to Vincent Delecroix
 Status changed from needs_review to positive_review
It is quite fragile then! It is not uncommon to have a bunch of vectors that we want to use to construct rows 0,...,k
and then feed a list for the k+1
th row.
Since it follows the design I guess it is what should be done...
comment:13 Changed 2 years ago by
Yea, I agree, but it probably requires a little larger of a change to fix it properly. Thank you for the review.
comment:14 Changed 2 years ago by
 Branch changed from public/linear_algebra/sparse_matrix_from_sparse_vectors18312 to 2044e5259d0b897c0b65d430c3c06f4a5444561a
 Resolution set to fixed
 Status changed from positive_review to closed
With my branch, I get:
New commits:
Faster construction of sparse matrix from list of sparse vectors.
Faster construction of sparse matrix from list of sparse vectors for matrix().
Fixing a few cases.