The Adaptive s-Step Conjugate Gradient Method

The performance of Krylov subspace methods on large-scale parallel computers is often limited by communication, or movement of data. This has inspired the development of s-step (or communication-avoiding) variants, in which iterations are computed in blocks of s. This reformulation can reduce the number of global synchronizations per iteration by a factor of $O(s)$ and has been shown to produce speedups in certain practical settings. Although the s-step variants are mathematically equivalent to their classical counterparts, they can behave quite differently in finite precision depending on the parameter s. If s is too large, the s-step method can suffer convergence delay and decreased attainable accuracy relative to the classical method. As a potential remedy to the loss of accuracy in s-step Krylov subspace methods, we introduce and analyze a variable s-step conjugate gradient method in which s may vary between blocks. From a bound on the growth of the residual gap in block k containing sₖ iterations we derive a constraint on the condition numbers of the computed O(sₖ)-dimensional Krylov subspace bases such that a desired accuracy is attainable. The analysis suggests that sₖ can be allowed to grow at a rate inversely proportional to the size of the computed residuals without affecting accuracy. We then introduce the adaptive s-step conjugate gradient method, a variable s-step approach which uses inexpensive estimates and a user-specified constraint on accuracy to automatically select an appropriate sₖ in each block. Our numerical experiments demonstrate that the adaptive s-step conjugate gradient method is able to attain up to the same accuracy as the classical conjugate gradient method in cases where the fixed s-step conjugate gradient method fails.