An efficient deflation technique for the communication-avoiding conjugate gradient

Carson, Erin ; Knight, Nicholas ; Demmil, James

Electronic transactions on numerical analysis, Tome 43 (2015).

Résumé

Summary: 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.

Détail

Classification : 65F08, 65F10, 65F50, 65Y05, 65Y20
Keywords: Krylov subspace methods, deflation, iterative solvers, minimizing communication, sparse matrices