Deflation-Based Spectral Preconditioning for the Conjugate Gradient Method on Perturbed Systems

Abstract

We consider sequences of large symmetric positive-definite linear systems in which spectral information from a reference matrix $A$ is reused to accelerate the solution of a nearby system with perturbed matrix $A(t)=A+tE$, where $E$ is symmetric, $\Vert E{\Vert }_F=1$, and $t\ge 0$ is the perturbation size. We compare deflated conjugate gradient (deflated CG) with preconditioned CG (PCG) equipped with a scaled spectral preconditioner constructed from the same spectral information of $A$. First, we derive an energy-norm error characterization of deflated CG. We then use perturbation analysis to show that, after one additional PCG iteration, the squared PCG error is bounded, up to terms of order $t^2$, by an explicit multiple of the squared deflated CG error. This result clarifies the role of the scaling parameter in the preconditioner. Experiments show that the scaled spectral preconditioner recovers much of the convergence improvement provided by deflation while requiring fewer products with $A(t)$.