mathnet
Post-multiplying Dense matrix by Sparse matrix super slow
I found that the order of multiplying a dense matrix by a sparse matix really matters:
- Sparse * Sparse -> Pretty much instant
- Sparse * Dense -> Very fast
- Dense * Dense -> Still fast
- Dense * Sparse -> Super slow, scales horribly with matrix size
These are the numbers I got for multiplying two identity matrices of the size shown on the x-axis (e.g. 200x200)
In the following discussion, @kadeanon mentioned:
From the implementation in MathNet, the performance issue stems from its lack of specialized handling for the Dense * Sparse matrix multiplication scenario. When the left operand is a dense matrix, the library fails to recognize that the right operand is sparse and instead falls back to a suboptimal general-purpose multiplication approach.
In short, we need to handle the Dense * Sparse case, leveraging sparse traversal, instead of falling back to the dense multiplication strategy.
