<p>check out Aydın Buluc, John R. Gilbert: <a href="https://arxiv.org/pdf/1006.2183" rel="nofollow noreferrer">Highly Parallel Sparse Matrix-Matrix Multiplication</a></p>
Algorithm for quadratic form matrix multiplication with sparse matrix
<p>I am optimizing code which heavily relies on a custom made Matrix library, (which won't be excluded from the project because it is everywhere. This is not nice, but it's a fact...) Many calculations are done with matrices of 10-20 rows and columns, many computations include a quadratic form like</p>
<pre><code>C = A*B*A'
</code></pre>
<p>I realized that often A is sparse and I would like to make use of this fact. So I am looking for an algorithm that would handle this case. Numerical stability is important. Is there anything I can use? (I didn't write our library so I don't know if there are any pitfalls I should take into account?)</p>
<p>As &quot;our&quot; simple O(n³) multiplication method executes faster than Eigen 3 on the target platform, as I need numerical stability and the matrices aren't very big, I guess that Strassen's algorithm as well as Coppersmith–Winograd algorithm aren't what I am looking for.  Instead it's just the quadratic form multiplication in a way that lets me easily check for zeros in A.</p>