A streaming approach for sparse matrix products and its application in galerkin multigrid methods

In this paper, we present a numerical algorithm for computing products of the form R K R^T, where R, R^T, and K are sparse matrices. By reformulating the problem into the simultaneous processing of a sequential data and control stream, cache miss penalties are significantly reduced. Even though the algorithm increases memory requirements, it accelerates sparse matrix products on recent processor architectures by a factor of up to 4 compared to previous approaches. We apply the algorithm to compute consistent system matrices at different resolution levels in a dynamic multigrid elasticity simulation, and we show its efficiency for nested and non-nested mesh hierarchies.