Volume 37, pp. 263-275, 2010.

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

Joachim Georgii and Rüdiger Westermann

Abstract

In this paper, we present a numerical algorithm for computing products of the form RKRT, where R,RT, 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.

Full Text (PDF) [711 KB], BibTeX

Key words

sparse matrix products, cache-awareness, multigrid, Galerkin update

AMS subject classifications

65F50, 65M55, 65M60, 65Y20, 68W01, 74B99, 74H15

Links to the cited ETNA articles

[4] Vol. 21 (2005), pp. 47-65 Rob H. Bisseling and Wouter Meesen: Communication balancing in parallel sparse matrix-vector multiplication
[20] Vol. 21 (2005), pp. 107-124 Ali Pinar and Virginia Vassilevska: Finding nonoverlapping substructures of a sparse matrix