Abstract:
The development of a memory-efficient sparse linear solver
requires careful attention to both algorithm design and implementation.
We present an alternative to the standard restarted GMRES algorithm
for solving a single right-hand side linear system 
based on
solving the block linear system 
. Additional starting vectors
and right-hand sides are chosen to accelerate convergence.
Algorithm performance, i.e. time to solution, is improved by using
the matrix 
in operations on groups of vectors, or
``multivectors,'' thereby reducing the movement of through
memory. The efficient implementation of our method depends on a
fast matrix-multivector multiply routine. We demonstrate the impact of
implementation choices on data movement and, as a result, algorithm
performance.
Home page
2004-04-24