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: sage-8.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:

Status badges

Description (last modified by nthiery)

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 nthiery

  • Description modified (diff)
  • Keywords sparse matrix constructor added

comment:2 Changed 4 years ago by tscrim

  • Authors set to Travis Scrimshaw
  • Branch set to public/linear_algebra/sparse_matrix_from_sparse_vectors-18312
  • Cc jdemeyer vdelecroix added
  • Commit set to 5a1fe385e9843ac1a4fde84075cb78d172d3e29e
  • Milestone changed from sage-6.7 to sage-8.1
  • Status changed from new to needs_review

With my branch, I get:

sage: n = 10^3
sage: F = FreeModule(QQ, n, sparse=True)
sage: v = F.an_element()
sage: vecs = [v]*n
sage: %time a = matrix(vecs, sparse=True)
CPU times: user 8 ms, sys: 0 ns, total: 8 ms
Wall time: 4.76 ms
sage: MS = MatrixSpace(QQ, n, sparse=True)
sage: %time b = MS(vecs)
CPU times: user 4 ms, sys: 0 ns, total: 4 ms
Wall time: 1.31 ms
sage: %time c = matrix(QQ, n, {(i,j): c for i,v in enumerate(vecs) for j,c in v.iteritems()}, sparse=True)
CPU times: user 4 ms, sys: 0 ns, total: 4 ms
Wall time: 2.93 ms

New commits:

f1acf03Faster construction of sparse matrix from list of sparse vectors.
774b510Faster construction of sparse matrix from list of sparse vectors for matrix().
5a1fe38Fixing a few cases.

comment:3 Changed 4 years ago by git

  • Commit changed from 5a1fe385e9843ac1a4fde84075cb78d172d3e29e to dff2da179d6042e6633bfa5d0dc09269b45158db

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

dff2da1Merge branch 'public/linear_algebra/sparse_matrix_from_sparse_vectors-18312' of git://trac.sagemath.org/sage into public/linear_algebra/sparse_matrix_from_sparse_vectors-18312

comment:4 Changed 4 years ago by tscrim

  • Milestone changed from sage-8.1 to sage-8.2

comment:5 Changed 3 years ago by sbrandhorst

  • Milestone changed from sage-8.2 to sage-8.3
  • Status changed from needs_review to needs_work
  • Work issues set to merge in develop

comment:6 Changed 3 years ago by vdelecroix

  • Milestone changed from sage-8.3 to sage-8.4

update milestone 8.3 -> 8.4

comment:7 Changed 2 years ago by git

  • Commit changed from dff2da179d6042e6633bfa5d0dc09269b45158db to c426c0c734bdb614c18b1a047dbe36e1d24bf86e

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

c426c0cExtended MatrixArgs to special case list of vectors when sparse.

comment:8 Changed 2 years ago by git

  • Commit changed from c426c0c734bdb614c18b1a047dbe36e1d24bf86e to 2044e5259d0b897c0b65d430c3c06f4a5444561a

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

2044e52Fixing a bug with rank.

comment:9 Changed 2 years ago by tscrim

  • Milestone changed from sage-8.4 to sage-8.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 vdelecroix

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 tscrim

I know, but that matches what sequence_type() does. So I am just following the same assumption.

comment:12 Changed 2 years ago by vdelecroix

  • 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 tscrim

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 vbraun

  • Branch changed from public/linear_algebra/sparse_matrix_from_sparse_vectors-18312 to 2044e5259d0b897c0b65d430c3c06f4a5444561a
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.