Minimizing communication in sparse matrix solvers
Authors:
Open Access
- 14 November 2009
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1-12
Abstract
Data communication within the memory system of a single processor node and between multiple nodes in a system is the bottleneck in many iterative sparse matrix solvers like CG and GMRES. Here k iterations of a conventional implementation perform k sparse-matrix-vector-multiplications and Ω(k) vector operations like dot products, resulting in communication that grows by a factor of Ω(k) in both the memory and network. By reorganizing the sparse-matrix kernel to compute a set of matrix-vector products at once and reorganizing the rest of the algorithm accordingly, we can perform k iterations by sending O(log P) messages instead of O(k · log P) messages on a parallel machine, and reading the matrix A from DRAM to cache just once, instead of k times on a sequential machine. This reduces communication to the minimum possible. We combine these techniques to form a new variant of GMRES. Our shared-memory implementation on an 8-core Intel Clovertown gets speedups of up to 4.3x over standard GMRES, without sacrificing convergence rate or numerical stability.Keywords
This publication has 15 references indexed in Scilit:
- Nonnegative Diagonals and High Performance on Low-Profile Matrices from Householder QRSIAM Journal on Scientific Computing, 2009
- Anatomy of high-performance matrix multiplicationACM Transactions on Mathematical Software, 2008
- Recycling Krylov Subspaces for Sequences of Linear SystemsSIAM Journal on Scientific Computing, 2006
- Sparsity: Optimization Framework for Sparse Matrix KernelsThe International Journal of High Performance Computing Applications, 2004
- A Newton basis GMRES implementationIMA Journal of Numerical Analysis, 1994
- Parallelizable restarted iterative methods for nonsymmetric linear systems. part I: TheoryInternational Journal of Computer Mathematics, 1992
- s-step iterative methods for symmetric linear systemsJournal of Computational and Applied Mathematics, 1989
- Implementation of the GMRES Method Using Householder TransformationsSIAM Journal on Scientific and Statistical Computing, 1988
- GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear SystemsSIAM Journal on Scientific and Statistical Computing, 1986
- The block conjugate gradient algorithm and related methodsLinear Algebra and its Applications, 1980