  Krylov subspace methods are widely known as efficient algebraic methods for
solving large scale linear systems. However, on massively parallel hardware the
performance of these methods is typically limited by communication latency
rather than floating point performance. With HPC hardware advancing towards the
exascale regime the gap between computation and communication keeps steadily
increasing, imposing the need for scalable alternatives to traditional Krylov
subspace methods. One such approach are the so-called pipelined Krylov subspace
methods, which reduce the number of global synchronization points and overlap
global communication latency with local arithmetic operations, thus hiding the
global reduction phases behind useful computations. To obtain this overlap the
traditional Krylov subspace algorithm is reformulated by introducing a number
of auxiliary vector quantities, which are computed using additional recurrence
relations. Although pipelined Krylov subspace methods are equivalent to
traditional Krylov subspace methods in exact arithmetic, local rounding errors
induced by the multi-term recurrence relations in finite precision may in
practice affect convergence significantly. This numerical stability study aims
to characterize the effect of local rounding errors on attainable accuracy in
various pipelined versions of the popular Conjugate Gradient method.
Expressions for the gaps between the true and recursively computed variables
that are used to update the search directions in the different CG variants are
derived. Furthermore, it is shown how these results can be used to analyze and
correct the effect of local rounding error propagation on the maximal
attainable accuracy of pipelined CG methods. The analysis in this work is
supplemented by numerical experiments that demonstrate the numerical behavior
of the pipelined CG methods.
