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_k$ iterations we derive a constraint on the condition numbers of the computed $O(s_k)$-dimensional Krylov subspace bases such that a desired accuracy is attainable. The analysis suggests that $s_k$ 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_k$ 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.