Efficient Sparse Matrix-Matrix Products Using Colorings

TitleEfficient Sparse Matrix-Matrix Products Using Colorings
Publication TypeJournal Article
Year of Publication2013
AuthorsMcCourt, M, Smith, BF, Zhang, H
Other NumbersANL/MCS-P5007-0813
AbstractSparse 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.