Opened 3 years ago

Closed 14 months ago

#26532 closed enhancement (fixed)

sparse matrix multiplication is slow

Reported by: tmonteil Owned by:
Priority: major Milestone: sage-9.2
Component: linear algebra Keywords:
Cc: Merged in:
Authors: Frédéric Chapoton, Travis Scrimshaw Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 2053489 (Commits, GitHub, GitLab) Commit: 2053489fe558b86aa5f6e7789afd0663b7045db0
Dependencies: Stopgaps:

Status badges

Description

As discussed on this ask question, multiplication of sparse matrices loops over lots of entries which is not convenient for very sparse matrices.

Change History (7)

comment:1 Changed 14 months ago by chapoton

  • Authors set to Frédéric Chapoton
  • Branch set to u/chapoton/26532
  • Commit set to 0bba07c056ba7e1eb2cee0bbc763cc1e7041b933
  • Milestone changed from sage-8.5 to sage-9.2
  • Status changed from new to needs_review

New commits:

0bba07cone detail in sparse matrices

comment:2 Changed 14 months ago by git

  • Commit changed from 0bba07c056ba7e1eb2cee0bbc763cc1e7041b933 to 787e2bc6fdc950cdec225fc3a9fc7908badcdc7e

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

787e2bcmore details in product of sparse matrices over QQ

comment:3 Changed 14 months ago by tscrim

  • Authors changed from Frédéric Chapoton to Frédéric Chapoton, Travis Scrimshaw
  • Branch changed from u/chapoton/26532 to public/matrix/speedup_sparse_mult-26532
  • Commit changed from 787e2bc6fdc950cdec225fc3a9fc7908badcdc7e to 2053489fe558b86aa5f6e7789afd0663b7045db0
  • Reviewers set to Travis Scrimshaw

I made a bunch of changes to try to improve the situation overall.

I did the same changes for the modn sparse matrices.

I also implemented the same thing for sparse integer matrices, which was using the default multiplication before:

sage: M = matrix([[0]*i+[1]+[0]*(50-i) for i in range(51)], sparse=True)
sage: type(M)
<class 'sage.matrix.matrix_integer_sparse.Matrix_integer_sparse'>
sage: %timeit M * M
The slowest run took 7.12 times longer than the fastest. This could mean that an intermediate result is being cached.
10000 loops, best of 5: 75.2 µs per loop
sage: M = matrix([[0]*i+[1]+[0]*(100-i) for i in range(101)], sparse=True)
sage: %timeit M * M
The slowest run took 5.40 times longer than the fastest. This could mean that an intermediate result is being cached.
1000 loops, best of 5: 248 µs per loop

versus before:

sage: M = matrix([[0]*i+[1]+[0]*(50-i) for i in range(51)], sparse=True)
sage: type(M)
<class 'sage.matrix.matrix_integer_sparse.Matrix_integer_sparse'>
sage: %timeit M * M
10000 loops, best of 5: 99.2 µs per loop
sage: M = matrix([[0]*i+[1]+[0]*(100-i) for i in range(101)], sparse=True)
sage: %timeit M * M
1000 loops, best of 5: 318 µs per loop

Finally, I did some micro improvements to the generic spare multiplication algorithm.


New commits:

170231fSome additional changes to rational sparse matrix mult.
c146ac0Making similar changes to matrix_modn_sparse.pyx.
e396cefAdding custom _matrix_times_matrix_ for sparse ZZ matrices.
0e6d768Making generic sparse tests actually test generic sparse matrices.
2053489Microimprovements and cleanup of generic sparse multiplication.

comment:4 Changed 14 months ago by chapoton

Thanks a lot. Looks good. Let us wait for the patchbots.

comment:5 Changed 14 months ago by chapoton

I think this is good to go. At least as a first good step. Travis, set to positive if you agree.

Last edited 14 months ago by chapoton (previous) (diff)

comment:6 Changed 14 months ago by tscrim

  • Status changed from needs_review to positive_review

Likely the next step would be pushing it further to use C++ data structures to avoid the extra Python overhead. There probably isn't too much more than can be optimized out with the current implementation of the generic sparse multiplication. The one thing that did bug me was the new_matrix being a Python function call and not some Cython implementation (as that is also used a lot in the matrix code).

Anyways, that aside, I also agree it is a good first step. Thank you for doing the initial optimization. That was very useful to work with.

comment:7 Changed 14 months ago by vbraun

  • Branch changed from public/matrix/speedup_sparse_mult-26532 to 2053489fe558b86aa5f6e7789afd0663b7045db0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.