PaperlayerView exact revision on arXiv

Source-linked AI summary

The Influence of the Cluster Point on Rounding Errors and Sensitivity in the Spectral Limited-Memory Preconditioner

Hisham Elzayyadi, Jemima M. Tabeart

arXiv:2609.27652v1math.NAcs.NA

TL;DR

Although sLMP commonly uses θ = 1, that choice can underperform unpreconditioned CG even with highly accurate spectral information, a behavior exact-arithmetic analysis does not explain. The paper derives cluster-point-dependent bounds for rounding errors and spectral perturbations, then uses numerical experiments to examine the predicted behavior. The findings indicate that cluster-point selection balances convergence and numerical stability according to the quality and structure of the available spectral information.

  • Problem

    Exact-arithmetic analyses do not explain why the commonly used θ = 1 can yield worse convergence than unpreconditioned CG, even when spectral information is highly accurate.

    Source: §1 · p. 2

  • Method

    The paper derives cluster-point-dependent bounds for rounding-error propagation during sLMP application and for sensitivity to inaccuracies in the dominant spectral information.

    Source: §1 · p. 2, §5 · p. 20

  • Results

    Numerical experiments show that the effect of inaccurate spectral information depends on eigenvector-error magnitude and direction: leakage can favor θ_WM,1/λ and θ_WM,e, while preserving the dominant invariant subspace restores the advantage of convergence-oriented choices.

    Source: §5 · p. 20

  • Takeaways & Limitations

    Cluster-point choice balances convergence and numerical stability according to the quality and structure of the available spectral information; preserving the dominant subspace indicates when exact-arithmetic theory remains predictive.

    Source: §5 · p. 20

    The rounding-error analysis uses the standard floating-point model, with unit roundoff u and nu < 1.

    Source: §3 · p. 4

Abstract

from arXiv · show

The spectral limited-memory preconditioner (sLMP) clusters leading eigenvalues of symmetric positive definite matrices to accelerate conjugate gradient (CG) convergence. In practice, the cluster point is often chosen to be unity. In some cases, however, this choice can fail to accelerate convergence relative to unpreconditioned CG, even when highly accurate spectral information is available. Alternative cluster points have been proposed based on exact-arithmetic convergence analysis, but such analysis does not explain this finite-precision behaviour. We study how the cluster point influences two sources of numerical error in sLMP-preconditioned CG. First, we analyse the propagation of floating-point rounding errors during application of the preconditioner and derive computable relative-error bounds. For the dominant subspace (spanned by the eigenvectors associated with the leading eigenvalues of the unpreconditioned system) and its orthogonal complement (spanned by the remaining eigenvectors), these bounds are minimized by a weighted median and a weighted arithmetic mean of the leading eigenvalues, respectively. Our analysis explains why small cluster points can strongly amplify errors in the dominant subspace. Second, we investigate sensitivity to perturbations in the dominant spectral information when constructing the preconditioner. The resulting perturbation bound is minimized by a weighted median of the perturbed dominant eigenvalues, with weights determined by the eigenvector perturbation magnitudes. Numerical experiments on synthetic problems illustrate the predicted rounding-error and sensitivity behaviour. Together, these results show that cluster-point selection in finite precision should account for exact-arithmetic convergence, rounding errors, and inaccuracies in the available spectral information.

1. Introduction.

The spectral limited-memory preconditioner (sLMP) clusters the dominant eigenvalues around a chosen point, often θ = 1. Exact-arithmetic analyses do not explain why θ = 1 can underperform unpreconditioned CG, motivating analysis of rounding errors and spectral-information inaccuracies.

1. Introduction.

  • The sLMP clusters the dominant eigenvalues around a prescribed cluster point θ, which is often set to 1 in practice.Prior exact-arithmetic work examined how θ affects spectral clustering and early CG convergence.Source: §1 · p. 2
  • Even with highly accurate spectral information, the standard choice θ = 1 may yield worse convergence than unpreconditioned CG.A cluster point favored by exact-arithmetic convergence analysis may still lead to poorer numerical behavior in practice.Source: §1 · p. 2
  • The paper analyzes how θ affects rounding-error propagation during sLMP application and sensitivity to inaccuracies in the spectral information used to construct it.For each error source, the authors derive bounds depending on θ and identify values that minimize those bounds.Source: §1 · p. 2

2. Background.

The background presents the limited-memory preconditioner and its spectral variant, then reviews cluster-point choices motivated by exact-arithmetic convergence. It closes by framing rounding errors and inaccurate spectral information as finite-precision effects to examine.

2. Background.

  • The LMP is parameterized by a full-column-rank matrix S with k ≪ n and a positive scalar θ.The displayed expression defines the preconditioner H_k.Source: §2 · p. 2
  • In the spectral variant, S contains eigenvectors for the k largest eigenvalues, and the dominant eigenvalues of the preconditioned operator are clustered at θ.The leading eigenvalues are ordered λ_1 ≥ λ_2 ≥ ··· ≥ λ_k > 0.Source: §2 · pp. 2–3
  • For implementation, the preconditioner can be applied as rank-one updates; the factorized form exposes coefficients α_i whose magnitudes depend on θ and influence error propagation.This representation is preferred over the compact implementation for improved numerical stability.Source: §2 · p. 3
  • Exact-arithmetic analyses provide reference choices including λ_k, λ_{k+1}, θ_r, and θ_m; θ_{k+1} is optimal within [λ_{k+1}, λ_k] for the stated convergence comparison.θ_r is described as the center of mass for the unmodified spectrum, weighted by components of the initial residual.Source: §2 · p. 3
  • The background transitions from exact-arithmetic results to investigating how cluster-point choice affects rounding errors and inaccuracies in the spectral information used to construct sLMP.Source: §2 · p. 3

3. Rounding-Error and Sensitivity Analysis.

The section separates finite-precision effects in sLMP into rounding errors during preconditioner application and errors in the spectral information used to construct it. It derives cluster-point choices for the two subspaces and shows that θ = 1 can produce poor practical convergence even with exact dominant spectral information.

3.1. Rounding-Error Analysis.

  • With exact dominant eigenpairs, practical sLMP with θ = 1 initially follows exact spectral clustering but its relative forward error rises substantially after about eight iterations.Exact spectral clustering improves convergence relative to unpreconditioned CG, isolating the practical method’s divergence from spectral inaccuracies.Source: §3.1 · p. 5
  • For complement-subspace rounding errors, the first-order upper bound is minimized by a weighted arithmetic mean of the dominant eigenvalues.The weights are w_i = 1/λ_i^2.Source: §3.1 · p. 6
  • For dominant-subspace rounding errors, the first-order bound is minimized by a weighted median of the dominant eigenvalues with weights 1/λ_i.Amplification is governed by λ1/θ below λk, θ/λk above λ1, and is constant at λ1/λk within [λk, λ1].Source: §3.1 · pp. 8–9

3.2. Sensitivity Analysis.

  • The sensitivity analysis addresses inaccuracies in the dominant eigenpairs, which are computed numerically in practice.The preceding rounding-error analysis assumes nearly exact spectral information.Source: §3.2 · p. 9

We define the perturbed quantities

The section bounds the effect of perturbations in the dominant eigenpairs on the preconditioner’s action. The bound is minimized by a weighted median of the perturbed dominant eigenvalues, with the exact-eigenvalue case reducing to a median of the unperturbed values.

We define the perturbed quantities

  • The analysis translates a bound on the perturbed preconditioner operator into a relative application-error bound, then selects θ to minimize that bound.The sensitivity-oriented choice incorporates information about the accuracy of the spectral information used to construct the preconditioner.Source: We define the perturbed quantities · pp. 10–11
  • The perturbation bound is minimized by a weighted median of the perturbed dominant eigenvalues.Theorem 3.8 assumes λ1 ≥ bλ1 ≥ bλ2 ≥ ··· ≥ bλk > 0; the weights reflect eigenvector perturbation magnitudes.Source: We define the perturbed quantities · pp. 10–11
  • When dominant eigenvalues are exact, the minimizing cluster point is a weighted median of the unperturbed dominant eigenvalues.This is the special case in which only the dominant eigenvectors are perturbed.Source: We define the perturbed quantities · p. 11
  • The paper identifies three error-informed choices: a weighted arithmetic mean for complement-subspace rounding, a weighted median for dominant-subspace rounding, and a perturbation-weighted median for inaccurate spectral information.These choices complement those motivated by exact-arithmetic convergence.Source: We define the perturbed quantities · p. 11

4. Numerical Results.

The numerical-results section states the computational environment and the synthetic matrix setup used for the experiments.

4. Numerical Results.

  • Experiments were performed in MATLAB R2024b on a 2.40 GHz 13th Gen Intel Core i7-13700H machine with 14 cores, 16 GB RAM, and Windows 11 Enterprise.Source: §4.1 · p. 12
  • The MATLAB code used to generate the numerical results is available from the paper’s stated GitHub repository.Source: §4.1 · p. 12
  • The experiments use synthetic symmetric positive definite matrices of size n = 5000, with the first k = 100 eigenpairs treated as dominant.Source: §4.1 · p. 12

4.1. Experimental setup.

The experiments test how rounding errors and spectral perturbations affect sLMP across controlled synthetic problems and approximate eigenpairs. The rounding-error tests show that small cluster points can be benign in the complement subspace yet strongly amplify error in the dominant subspace.

4.1. Experimental setup.

  • For synthetic experiments, the approximate dominant basis is constructed using prescribed perturbation magnitudes for its eigenvectors, with perturbation directions controlled separately and followed by orthonormalization.In practical experiments, dominant eigenpairs are approximated using randomized Nyström [9, 4] and REVD-ritzit.Source: §4.1 · p. 12
  • Perturbations are characterized by measures of dominant-subspace mixing, complement-subspace leakage, and the sine of the largest principal angle between exact and approximate dominant subspaces.Comparisons include unpreconditioned CG, exact-arithmetic cluster points, and error-informed choices.Source: §4.1 · p. 12
  • The complement-subspace rounding-error bound is minimized at θWAM, and observed error stays near machine precision for small θ, including θ = 1.Observed complement error increases above the dominant spectrum but remains comparatively small.Source: §4.2 · p. 13, Figure 2 · p. 13
  • The dominant-subspace bound is minimized at θWM,1/λ; error rises rapidly below λk and is several orders larger near θ = λn = 1.The reported increase explains the deterioration of practical sLMP with θ = 1.Source: §4.2 · p. 13
  • Small cluster points can strongly amplify dominant-subspace rounding errors while remaining benign in the complement, whereas θ near λk gives small errors in both subspaces.The dominant subspace therefore imposes the more restrictive stability requirement.Source: §4.2 · p. 13

4.3. Synthetic perturbations.

Synthetic perturbation experiments show that both perturbation direction and magnitude shape the practical performance of sLMP. Large leakage favors error-analysis cluster points, while eliminating or sufficiently reducing leakage restores the advantage of convergence-oriented choices.

4.3. Synthetic perturbations.

  • The synthetic tests vary perturbation direction and magnitude, while a further experiment uses approximate dominant eigenpairs from practical eigensolvers.The reference cluster points are retained from exact-arithmetic convergence analysis.Source: §4.3 · p. 14, §4.4 · p. 17

4.3.1. Large perturbations with unrestricted directions.

  • With large unrestricted perturbations, θWM,e and θWM,1/λ converge fastest, while λk+1, θr, and θm deteriorate and initially increase relative error.θWM,e gives the smallest relative error; substantial leakage into the complement accompanies the regime in which error-analysis choices outperform exact-arithmetic choices.Source: §4.3.1 · p. 14, Figure 3 · p. 15

4.3.2. Large perturbations confined to the dominant subspace.

  • With large perturbations confined to the dominant subspace, θm converges fastest, followed by θr and λk+1; θWM,e and θWM,1/λ are less effective.The dominant subspace is preserved up to roundoff despite substantial eigenvector perturbations, and the comparison indicates that leakage—not dominant-subspace mixing alone—primarily caused the prior deterioration.Source: §4.3.2 · pp. 14–15, Figure 4 · p. 16

4.3.3. Small perturbations with unrestricted directions.

  • When unrestricted perturbation magnitudes are reduced to τi ∈[10−12, 10−6], convergence-oriented cluster points again converge fastest and error-informed choices lose their earlier advantage.Leakage remains but is several orders of magnitude smaller; both δi and ηi decrease, leaving insufficient leakage to significantly modify the dominant subspace.Source: §4.3.3 · p. 16, Figure 5 · p. 17

4.3. Synthetic perturbations.

  • Across the experiments, large leakage favors error-analysis choices, whereas eliminating or sufficiently reducing leakage restores the superiority of convergence-oriented choices.The results identify perturbation direction and magnitude as determining whether exact-arithmetic convergence theory remains predictive in finite precision.Source: §4.3.3 · p. 16

4.4. Practical eigensolvers.

Across the practical eigensolvers, convergence-oriented cluster points perform best when the dominant subspace is preserved, while the two methods produce different perturbation structures. The Nyström weighted-median choice can suppress a particularly inaccurate eigenvector, whereas REVD-ritzit errors are largely confined to the dominant subspace.

4.4.1. Randomized Nystr¨om Algorithm.

  • For Nyström, θm, θr, and λk+1 converge fastest and nearly coincide, while θWM,1/λ and bλk converge more slowly.In this experiment, θWM,e = bλk.Source: §4.4 · p. 17
  • The global leakage measure is 1.863 × 10−3, but leakage is strongly localized, with the final approximate eigenvector providing the dominant contribution.Source: §4.4.1 · p. 17
  • The Nyström weighted-median choice sets the coefficient of the most perturbed eigenvector to zero, excluding that eigenvector from sLMP.The remaining computed eigenvectors are highly accurate, so the overall perturbation remains limited and convergence-oriented choices retain their advantage.Source: §4.4.1 · p. 18

4.4.2. REVD-ritzit.

  • For REVD-ritzit, θm, θr, and λk+1 yield the smallest relative errors, while θWM,1/λ, θWM,e, and bλk converge more slowly.The convergence pattern resembles the synthetic experiment with perturbations confined to the dominant subspace.Source: §4.4.2 · pp. 18–19
  • REVD-ritzit shows substantial mixing among dominant eigenvectors but comparatively little leakage into the complement, leaving that subspace largely preserved.Despite large individual eigenvector perturbations, the perturbation is almost entirely confined to the dominant subspace.Source: §4.4.2 · p. 19

4.4. Practical eigensolvers.

  • Both eigensolvers support dominant-subspace preservation as the main indicator of whether convergence-oriented cluster points retain their advantage, despite different perturbation structures.Nyström concentrates error in the final dominant eigenvectors; REVD-ritzit distributes it more uniformly while largely preserving the dominant subspace.Source: §4.4.1 · p. 18, §4.4.2 · p. 19

5. Conclusion.

The conclusion weighs convergence against finite-precision effects and spectral-information errors in choosing the sLMP cluster point. Experiments find that the structure of eigenvector errors affects which choices perform well, while dominant-subspace preservation helps indicate when exact-arithmetic predictions remain useful.

5. Conclusion.

  • Rounding-error bounds identify θWM,1/λ as a finite-precision choice for the dominant subspace and explain the poor practical behaviour of θ = 1.The analysis derives relative forward-error bounds for both the dominant and complement subspaces.Source: §5 · p. 20
  • The spectral-perturbation bound accounts for dominant-eigenvector and eigenvalue errors and is minimized by θWM,e, a weighted median of perturbed dominant eigenvalues weighted by eigenvector perturbation magnitudes.Because these magnitudes are generally unavailable in practice, θWM,e primarily serves as a theoretically optimal reference.Source: §5 · p. 20
  • Experiments find that significant leakage into the complement can favour θWM,1/λ and θWM,e, whereas preserving the dominant invariant subspace restores the advantage of convergence-oriented choices.In the cases considered, eigenvalue inaccuracies have a comparatively small additional effect; λk can provide a useful compromise when other convergence-oriented choices deteriorate.Source: §5 · p. 20
  • Cluster-point choice balances convergence and numerical stability according to the quality and structure of spectral information; lower-precision arithmetic remains a direction for future study.Preservation of the dominant subspace is an indicator of when exact-arithmetic convergence theory remains predictive of practical behaviour.Source: §5 · p. 20
Loading 2609.27652v1…