Reducing Memory Access Costs: Variants of GMRES

Allison Baker, University of Colorado

Each year the gap between CPU performance and memory access time continues to grow. For this reason, reducing memory access costs is a key component to solving very large sparse systems of linear equations efficiently. In particular, efficient data re-use is crucial to reducing memory access costs. Therefore, we are exploring alternatives to the standard GMRES algorithm based on blocking the sparse matrix operations. Currently, we are focusing on alternatives to solving the single right-hand side system based on solving the block linear system AX=B, where X and B are both matrices.

To use a block system to solve a single right-hand side system, additional starting vectors and right-hand sides are chosen. Ideally these additional vectors are chosen in a way that accelerates convergence to the solution. To gain insight into choosing appropriate additional right-hand sides, we have studied augmenting GMRES with various families of vectors that can significantly affect performance. We present a new algorithm that accelerates convergence by augmenting the standard GMRES approximation space with approximations to the error. We compare our algorithm to existing acceleration schemes, discuss the theory, present numerical results, and explain the natural extension to a block method.

The ultimate goal is to achieve balance between increasing efficiency of an algorithm from a memory-usage standpoint and maintaining favorable numerical properties. The resulting reduction in time to solve large sparse linear systems will benefit many science and engineering disciplines.

Abstract Author(s): Allison Baker