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:  sage9.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 sage8.5 to sage9.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_mult26532
 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]*(50i) 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]*(100i) 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]*(50i) 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]*(100i) 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_mult26532 to 2053489fe558b86aa5f6e7789afd0663b7045db0
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
one detail in sparse matrices