Advancements in the eld of high-performance scientic computing are necessary to address
the most important challenges we face in the 21st century. From physical modeling to largescale
data analysis, engineering ecient code at the extreme scale requires a critical focus
on reducing communication { the movement of data between levels of memory hierarchy or
between processors over a network { which is the most expensive operation in terms of both
time and energy at all scales of computing. Achieving scalable performance thus requires
a dramatic shift in the eld of algorithm design, with a key area of innovation being the
development of communication-avoiding algorithms.
Solvers for sparse linear algebra problems, ubiquitous throughout scientic and mathematical
applications, often limit application performance due to a low computation/communication
ratio. Among iterative methods, Krylov subspace methods are the most general
and widely-used. To alleviate performance bottlenecks, much prior work has focused on the
development of communication-avoiding Krylov subspace methods, which can oer asymptotic
performance improvements over a set number of iterations.
In nite precision, the convergence and stability properties of classical Krylov methods are
not necessarily maintained by communication-avoiding Krylov methods. Depending on the
parameters used and the numerical properties of the problem, these communication-avoiding
variants can exhibit slower convergence and decreased accuracy compared to their classical
counterparts, making it unclear when communication-avoiding Krylov subspace methods are
suitable for use in practice.
Until now, the literature on communication-avoiding Krylov methods lacked a detailed
numerical stability analysis, as well as both theoretical and practical comparisons with the
stability and convergence properties of standard implementations. In this thesis, we address
this major challenge to the practical use of communication-avoiding Krylov subspace methods.
We extend a number of theoretical results and algorithmic techniques developed for
classical Krylov subspace methods to communication-avoiding Krylov subspace methods and
identify constraints under which these methods are competitive in terms of both achieving
asymptotic speedups and meeting application-specic numerical requirements.

Technical Report