sparse matrix multiplication is slow

[tmonteil]

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

[chapoton]

New commits:

​0bba07c

one detail in sparse matrices

[git]

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

​787e2bc

more details in product of sparse matrices over QQ

[tscrim]

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.

[chapoton]

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

[chapoton]

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

[tscrim]

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.