Source-linked AI summary
Deflation-Based Spectral Preconditioning for the Conjugate Gradient Method on Perturbed Systems
Youssef Diouane, Selime Gürol, Oussama Mouhtal, Dominique Orban
TL;DR
For sequences of nearby SPD systems, the paper asks how spectral information from a reference matrix can be reused to accelerate CG when building a preconditioner may be costly. It compares deflated CG with PCG using a scaled spectral preconditioner and analyzes their errors under perturbation. After one additional PCG iteration, its squared error is bounded by an explicit multiple of the squared deflated-CG error, up to higher-order perturbation terms.
Problem
Reusing spectral information from a reference matrix could accelerate CG on a nearby perturbed system, while constructing a preconditioner may be prohibitively expensive in large matrix-free settings.
Source: §1 · p. 1Method
The paper characterizes deflated CG’s energy-norm error and uses first-order perturbation analysis to compare it with PCG using a scaled spectral preconditioner built from the reference matrix’s spectral information.
Source: §1 · p. 2Results
After one additional PCG iteration, its squared energy-norm error is bounded by an explicit multiple of deflated CG’s squared error plus higher-order terms in t.
Source: §1 · p. 2Takeaways & Limitations
Numerical experiments show that the scaled spectral preconditioner closely reproduces deflated CG’s convergence while avoiding the deflation projector and its associated products with the perturbed matrix.
Source: §5 · p. 19The analysis fixes the perturbation direction E and varies only its magnitude; extending it to multiple eigenvalues or a class of symmetric perturbations remains future work.
Source: §5 · p. 19
Abstract
from arXiv · showhide
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, $\|E\|_F=1$, and $t\geq0$ 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)$.
1. Introduction.
The paper studies reuse of spectral information from a reference matrix to accelerate CG on a nearby perturbed system. It compares deflated CG with a scaled spectral preconditioner and develops a theoretical link between their errors.
1. Introduction.
- Reusing information across nearby systems is attractive in large matrix-free settings, where constructing a preconditioner may be prohibitively expensive and matrix–vector products are limited.Source: §1 · p. 1
- Deflated CG splits the solution into a deflation-subspace component and a complementary component computed by CG, but forming and solving with W⊤A(t)W requires additional products with the perturbed matrix.The solve generally needs to be accurate because deflated CG can be sensitive to errors in it.Source: §1 · pp. 1–2
- Earlier analysis of the scaled spectral preconditioner assumed exact spectral information from the system matrix, leaving reuse from a nearby matrix unexplained.The preconditioner maps selected eigenvalues to a common value θ, and prior experiments found that suitable scaling could reproduce much of deflation’s convergence acceleration at lower initialization cost.Source: §1 · p. 2
- After one additional PCG iteration, first-order perturbation analysis bounds its squared energy-norm error by an explicit multiple of deflated CG’s squared error plus higher-order terms in t.The analysis focuses on eigenpairs associated with the largest eigenvalues of A, but extends to any selected subset; it also clarifies how θ should relate to the nondeflated spectrum.Source: §1 · p. 2
2. Deflated conjugate gradient.
Deflated CG separates the solution into a component in a chosen subspace and a complementary component obtained from a projected system. In exact arithmetic, that projected solve is equivalent to a reduced CG system and yields an energy-norm error characterization.
2. Deflated conjugate gradient.
- Deflated CG decomposes the solution into a component in the deflation subspace and a complementary component computed by CG on a projected system.Source: §2 · p. 3
- The projected system is consistent and positive semidefinite, and solving it by CG is equivalent to solving a reduced system of dimension n−k.The reduced system uses the nonzero eigenvalues of the projected matrix.Source: §2 · p. 3
- In exact arithmetic, CG solves the reduced system in at most n−k iterations, while the null-space component of the initial vector remains unchanged.The final iterate combines that unchanged component with the component in the projected matrix’s range that solves the projected system.Source: §2 · p. 4
- Proposition 2.2 gives an energy-norm characterization of the deflated CG error.Source: §2 · p. 4
3. Deflated CG and PCG for a perturbed system.
This section formulates deflated CG and scaled spectral PCG using reference-matrix spectral information, then analyzes their errors on perturbed systems, deriving a second-order comparison and identifying scaling choices that make its leading factor contractive for sufficiently small perturbations.
3. Deflated CG and PCG for a perturbed system.
- Deflated CG uses the k eigenvectors associated with the largest eigenvalues of A, while PCG uses a scaled spectral preconditioner constructed from that spectral information.The preconditioner is parameterized by θ.Source: §3 · p. 5
3.1. Perturbation analysis.
- For simple eigenvalues, the perturbation analysis supplies second-order eigenpair remainder bounds with explicit constants and a validity range determined by the spectral gap.The stated range is 0 ≤ t ≤ gi/(4∥E∥2), where gi is the gap around λi.Source: §3.1 · p. 5
3.2. Deflated CG for the perturbed system.
- Deflated CG’s energy-norm error is explicitly characterized through residual coefficients and a best degree-ℓ polynomial approximation over the nonzero spectrum of the projected operator.The theorem applies for 1 ≤ ℓ < n − k and any starting vector.Source: §3.2 · p. 7
- The projected matrix’s nonzero eigenvalues and eigenvectors, along with the projected right-hand side, admit first-order perturbation expansions with O(t^2) remainders.These expansions are derived under Assumption 3.1 for sufficiently small t.Source: §3.2 · pp. 8–9
3.3. Perturbation analysis of the preconditioned matrix.
- For nondeflated eigenvalue branches, the preconditioned matrix has eigenpair expansions with O(t^2) remainders uniformly over scaling parameters separated from the nondeflated spectrum.The separation is at least δ from λk+1 through λn.Source: §3.3 · pp. 9–10
3.4. Comparison between PCG and deflated CG.
- Under the stated initial-guess assumptions, squared residual coefficients for PCG and deflated CG agree up to O(t^2); spectral intervals also bound the projected and preconditioned matrices.The coefficient estimate is uniform over the admissible scaling parameters; the intervals apply for 0 ≤ t ≤ t0 with t0∥E∥2 < λn.Source: §3.4 · pp. 10–12
- After one additional PCG iteration, the squared energy-norm error is bounded by the squared deflated-CG error times (α(t, θ)/θ)^2, plus an O(t^2) remainder.The leading factor is contractive when α(t, θ)/θ < 1.Source: §3.4 · pp. 12, 13, 15
- The perturbation remainder bound may grow rapidly with iteration index ℓ when qk > 1, but this reflects estimate quality, not increasing error in either method.When 0 < qk < 1, the bound may instead decrease with ℓ; increasing k may reduce qk by removing more eigenvalues from the nondeflated spectrum.Source: §3.4 · p. 15
- For sufficiently small t, θ = λk gives a contractive leading factor; if λn is known and θm avoids the nonzero spectrum, θm = (λk + λn)/2 gives a strictly smaller factor.The midpoint choice is particularly practical in variational data assimilation, where λn is often known a priori.Source: §3.4 · p. 15
4. Numerical experiments.
The experiments compare the theoretical-bound behavior and energy-norm convergence of PCG with deflated CG, while also contrasting the methods’ computational costs.
4.1. Computational complexity: PCG versus deflated CG.
- Deflated CG requires k products with A(t) to form its projector, whereas PCG with U θ stores only S_k, the associated eigenvalues, and scalar θ.Applying U θ uses multiplications by S_k and S_k⊤ plus diagonal scaling.Source: §4.1 · p. 16
4.2. Synthetic data experiments.
- The synthetic tests use n = 4 × 10^3, λ1 = 10^6, λn = 1, ψ = 1, and a fixed symmetric E with ∥E∥F = 1.The spectrum has exponential decay controlled by ρ, and ψ ensures a positive lower bound on the minimum consecutive eigenvalue gap.Source: §4.2 · p. 16
- The experiments compare the PCG error with Theorem 3.8’s leading bound term, then compare CG, PCG, and deflated CG over selected k, θ, and t values.For the bound comparison, k = 60 and θm are used, with α(t, θm)/θm ≈ 0.99 over the tested perturbations.Source: §4.2 · p. 16, §4.2.1 · p. 16, §4.2.2 · p. 17
4.2.1. Comparison with the theoretical bound.
- The leading bound term can fall below PCG error as ℓ grows; for ρ = 0.9, ℓ = 40, the discrepancy shrinks for small t.For ρ = 0.94, it falls below the error near t = 1 at ℓ = 50 and once t exceeds 10^-6 at ℓ = 60. The omitted O(t^2) remainder, governed by q_k, explains why this does not contradict Theorem 3.8 and can become large for large ℓ.Source: §4.2.1 · pp. 16–17, Figure 4.1 · p. 17, Figure 4.2 · p. 17
4.2.2. Comparison of energy-norm errors.
- For ρ = 0.9 and 0.94, PCG(U θm) substantially improves upon CG and closely follows deflated CG at moderate accuracy; differences are most visible at high accuracy for t = 1.Increasing k from 60 to 80 reduces the gap between PCG(U θm) and deflated CG, especially during the final iterations.Source: §4.2.2 · p. 18
5. Conclusion.
The paper compares deflated CG with PCG using a scaled spectral preconditioner built from the same selected eigenvectors of a reference matrix. Its analysis and experiments support the preconditioner as an alternative for closely related systems, within stated perturbation limits.
5. Conclusion.
- The scaled spectral preconditioner closely reproduces deflated CG convergence while avoiding construction of the deflation projector and its associated products with the perturbed matrix.The comparison uses the same selected eigenvectors of A for both methods.Source: §5 · p. 19
- After one additional PCG iteration, the squared PCG error is bounded by an explicit multiple of the squared deflated CG error, up to higher-order perturbation terms.The comparison combines an energy-norm characterization of deflated CG with first-order perturbation analysis.Source: §5 · p. 19
- The analysis assumes simple eigenvalues and a fixed perturbation direction E; extending it to multiple eigenvalues and classes of symmetric perturbations remains future work.The paper varies the perturbation magnitude t while fixing E.Source: §5 · p. 19