Title: Communication-avoiding Krylov subspace methods

Speaker: Mark Hoemmen, CSRI Postdoctoral Seminar, SNL 1416 and UC Berkeley         

Date/Time: Friday, January 22, 2010, 1:00 – 2:00 pm        

Location: CSRI Building/Room 90 (Sandia NM)

Brief Abstract: Krylov subspace methods (KSMs) are numerical algorithms for solving large, sparse linear systems of equations and eigenvalue problems. Although they are commonly used and often highly optimized, most KSMs achieve only a small fraction of peak arithmetic performance of the computers on which they are run.  This occurs on almost all computers, from workstations to massively parallel supercomputers.  The cause is that the performance of most commonly used KSMs is bound by the speed of communication -- moving data between processors or between levels of the memory hierarchy -- rather than by the speed of arithmetic. Communication is much slower than arithmetic, and is only getting slower relative to arithmetic as hardware evolves.

In my thesis, I propose new "communication-avoiding" Krylov methods. These require much less data movement between levels of the memory hierarchy, and between processors in parallel, than standard KSMs. Our single-node shared-memory parallel implementation of a communication-avoiding version of GMRES also achieves significant speedups over a parallel version of standard GMRES running on the same number of processors.

In this talk, I will give an overview of these new Krylov methods, which replace the standard versions of Arnoldi iteration, GMRES, symmetric Lanczos, and CG, both with and without preconditioning.  I will explain how one makes them numerically stable in practice.  Also, I will talk about the computational kernels which make these new KSMs communication-avoiding, and show that they must be tuned simultaneously ("co-tuned") for best performance.

CSRI POC: Erik Boman, 505/844-2003