Opened 4 years ago
Closed 2 years 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 2 years 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 2 years 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 2 years 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 2 years ago by
Thanks a lot. Looks good. Let us wait for the patchbots.
comment:5 Changed 2 years 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 2 years 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 2 years 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