Volume 43, pp. 125-141, 2014-2015.

An efficient deflation technique for the communication-avoiding conjugate gradient method

Erin Carson, Nicholas Knight, and James Demmel

Abstract

By fusing $s$ loop iterations, communication-avoiding formulations of Krylov subspace methods can asymptotically reduce sequential and parallel communication costs by a factor of $O(s)$. Although a number of communication-avoiding Krylov methods have been developed, there remains a serious lack of available communication-avoiding preconditioners to accompany these methods. This has stimulated active research in discovering which preconditioners can be made compatible with communication-avoiding Krylov methods and developing communication-avoiding methods which incorporate these preconditioners. In this paper we demonstrate, for the first time, that deflation preconditioning can be applied in communication-avoiding formulations of Lanczos-based Krylov methods such as the conjugate gradient method while maintaining an $O(s)$ reduction in communication costs. We derive a deflated version of a communication-avoiding conjugate gradient method, which is mathematically equivalent to the deflated conjugate gradient method of Saad et al. [SIAM J. Sci. Comput., 21 (2000), pp.1909–1926]. Numerical experiments on a model problem demonstrate that the communication-avoiding formulations can converge at comparable rates to the classical formulations, even for large values of $s$. Performance modeling illustrates that $O(s)$ speedups are possible when performance is communication bound. These results motivate deflation as a promising preconditioner for communication-avoiding Krylov subspace methods in practice.

Full Text (PDF) [346 KB], BibTeX

Key words

Krylov subspace methods, deflation, iterative solvers, minimizing communication, sparse matrices

AMS subject classifications

65F08, 65F10, 65F50, 65Y05, 65Y20

Links to the cited ETNA articles

[25]	Vol. 39 (2012), pp. 156-185 Martin H. Gutknecht: Spectral deflation in Krylov solvers: a theory of coordinate space based methods
[41]	Vol. 40 (2013), pp. 381-406 Desire Nuentsa Wakam and Jocelyne Erhel: Parallelism and robustness in GMRES with a Newton basis and deflated restarting