Krylov Subspace Recycling for Sequences of Shifted Linear Systems

Abstract

We study the use of Krylov subspace recycling for the solution of a sequence of slowly-changing families of linear systems, where each family consists of shifted linear systems that differ in the coefficient matrix only by multiples of the identity. Our aim is to explore the simultaneous solution of each family of shifted systems within the framework of subspace recycling, using one augmented subspace to extract candidate solutions for all the shifted systems. The ideal method would use the same augmented subspace for all systems and have fixed storage requirements, independent of the number of shifted systems per family. We show that a method satisfying both requirements cannot exist in this framework. As an alternative, we introduce two schemes. One constructs a separate deflation space for each shifted system but solves each family of shifted systems simultaneously. The other builds only one recycled subspace and constructs approximate corrections to the solutions of the shifted systems at each cycle of the iterative linear solver while only minimizing the base system residual. At convergence of the base system solution, we apply the method recursively to the remaining unconverged systems. We present numerical examples involving systems arising in lattice quantum chromodynamics.

5 figures, 20 pages (main paper 18 pages + refs 2 pages)

References in corpus (4)

• Many Masses on One Stroke: Economic Computation of Quark Propagators
• Computing and deflating eigenvalues while solving multiple right hand side linear systems in Quantum Chromodynamics
• Deflated GMRES for Systems with Multiple Shifts and Multiple Right-Hand Sides
• Seed methods for linear equations in lattice qcd problems with multiple right-hand sides

Cited by in corpus (14)

• Block Krylov subspace recycling for shifted systems with unrelated right-hand sides
• GMRES algorithms over 35 years
• Restarted Hessenberg method for solving shifted nonsymmetric linear systems
• Low Rank Approximation in $G_0{W}_0$ Approximation
• Computational methods for large-scale inverse problems: a survey on hybrid projection methods
• A flexible and adaptive Simpler GMRES with deflated restarting for shifted linear systems
• Efficient variants of the CMRH method for solving a sequence of multi-shifted non-Hermitian linear systems simultaneously
• Preconditioned Recycling Krylov subspace methods for self-adjoint problems
• Two recursive GMRES-type methods for shifted linear systems with general preconditioning
• Preconditioning the Restarted and Shifted Block FOM Algorithm for Matrix Exponential Computation
• Efficient Computation of Gaussian Likelihoods for Stationary Markov Random Field Models
• Hybrid Projection Methods with Recycling for Inverse Problems
• Breaking the $O(1/\epsilon )$ Optimal Rate for a Class of Minimax Problems
• Recycling BiCG for families of shifted linear systems