Sparse Matrix-Matrix Products Executed Through Coloring

Sparse matrix-matrix products appear in multigrid solvers among other applications. Some implementations of these products require the inner product of two sparse vectors. In this paper, we propose a new algorithm for computing sparse matrix-matrix products by exploiting their nonzero structure through the process of graph coloring. We prove the validity of this technique in general and demonstrate its viability for examples including multigrid methods used to solve boundary value problems as well as matrix products appearing in unstructured applications.