Enlarged Krylov Subspace Conjugate Gradient Methods for Reducing Communication

In this paper we introduce a new approach for reducing communication in Krylov subspace methods that consists of enlarging the Krylov subspace by a maximum of t vectors per iteration, based on a domain decomposition of the graph of A. The obtained enlarged Krylov subspace Kk,t(A,r₀) is a superset of the Krylov subspace Kₖ(A,r₀), Kₖ(A,r₀) ⊂ Kk,t(A,r₀). Thus, we search for the solution of the system $Ax=b$ in Kk,t(A,r₀) instead of Kₖ(A,r₀). Moreover, we show in this paper that the enlarged Krylov projection subspace methods lead to faster convergence in terms of iterations and parallelizable algorithms with less communication, with respect to Krylov methods.