AN EFFICIENT DEFLATION TECHNIQUE FOR THE COMMUNICATION- AVOIDING CONJUGATE GRADIENT METHOD ∗

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 num- ber 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 discov- ering 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 co mmunication-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-avoidin g conjugate gradient method, which is mathemati- cally 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 illus- trates 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.