Opened 2 years ago
Closed 10 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: |
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 11 months ago by
- 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
comment:2 Changed 11 months ago by
- Commit changed from 0bba07c056ba7e1eb2cee0bbc763cc1e7041b933 to 787e2bc6fdc950cdec225fc3a9fc7908badcdc7e
Branch pushed to git repo; I updated commit sha1. New commits:
787e2bc | more details in product of sparse matrices over QQ
|
comment:3 Changed 11 months ago by
- 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:
170231f | Some additional changes to rational sparse matrix mult.
|
c146ac0 | Making similar changes to matrix_modn_sparse.pyx.
|
e396cef | Adding custom _matrix_times_matrix_ for sparse ZZ matrices.
|
0e6d768 | Making generic sparse tests actually test generic sparse matrices.
|
2053489 | Microimprovements and cleanup of generic sparse multiplication.
|
comment:4 Changed 11 months ago by
Thanks a lot. Looks good. Let us wait for the patchbots.
comment:5 Changed 11 months ago by
I think this is good to go. At least as a first good step. Travis, set to positive if you agree.
comment:6 Changed 11 months ago by
- 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 10 months ago by
- Branch changed from public/matrix/speedup_sparse_mult-26532 to 2053489fe558b86aa5f6e7789afd0663b7045db0
- Resolution set to fixed
- Status changed from positive_review to closed
New commits:
one detail in sparse matrices