Sparse matrix-matrix products appear in multigrid solvers and computational methods for graph theory. Some formulations of these products require the inner product of two sparse vectors, which have inefficient use of cache memory. In this paper, we propose a new algorithm for computing sparse matrix-matrix products by exploiting matrix nonzero structure through the process of graph coloring. We prove the validity of this technique in general and demonstrate its viability for multigrid methods used to solve three-dimensional boundary value problems.

%G eng %1 http://www.mcs.anl.gov/papers/P5007-0813_1.pdf