Krylov Subspace Recycling: A Direct Projection Method for Solving Shifted Linear Systems

Kirk Soodhalter^*

We address the solution of a sequence of families of linear systems. For the $i$th family, there is a base coefficient matrix $A_{i}$, and the coefficient matrices for all systems in the $i$th family differ from $A_{i}$ by a multiple of the identity, i.e., \[ A_{i}x_{i}=b_{i}\quad \mbox{ and }\quad (A_{i}+\sigma_{i}^{(\ell)} I)x_{i}^{(\ell)} = b_{i}\quad \mbox{ for }\quad \ell=1\ldots L_{i}, \] where $L_{i}$ is the number of shifts at step $i$. This is an important problem arising in various applications. \newline The recycled GMRES method [Parks et al., SIAM J. Sci. Comput., 2006] is an extension of GMRES in which the minimum residual projection is performed over an augmented Krylov subspace. The formulation of recycled GMRES allows for minimization over arbitrary augmented subspaces. For solving a sequence of linear systems, this allows us to use a subspace of the search space generated when solving system $i$ to augment the Krylov subspace generated for system $i+1$. \newline We extend the machinery of the Recycled GMRES method to minimize the residuals of the shifted systems by direct projection. All approximations come from the same augmented Krylov subspace, but for each shifted system, the approximation is chosen according to a different constraint. The constraints are chosen such that the approximations can be computed efficiently. Upon convergence of the iteration for the base system, the shifted system iterations will not necessarily have converged. In this situation, the method can be called recursively for the remaining unconverged systems. We present analysis of this method and numerical results involving systems arising in lattice quantum chromodynamics.

Mathematics Subject Classification: 65F10 65F50

Keywords: Krylov subspaces methods; subspace recycling; shifted systems; GMRES; deflation

Minisymposion: Iterative Methods for Ill-Posed Problems