PaperlayerView exact revision on arXiv

Source-linked AI summary

Global Convergence of Hessenberg Shifted QR II: Numerical Stability

Jess Banks, Jorge Garza-Vargas, Nikhil Srivastava

arXiv:2205.06810v1math.NAcs.DScs.NA

TL;DR

Finite-arithmetic shifted QR lacks a complete rapid-convergence analysis because backward stability does not control forward behavior or Ritz-value computation. The paper combines random shift regularization with an optimal-Ritz-value/early-decoupling dichotomy, showing that the Part I strategy converges rapidly with polylogarithmic precision under controlled conditioning and eigenvalue gaps. Its guarantees rely on auxiliary small-eigenvalue algorithms and remain aimed at rigorous worst-case analysis rather than direct software deployment.

  • Problem

    Finite-arithmetic shifted QR requires forward stability and reliable approximate Ritz values, but existing analyses do not provide a complete rapid-convergence proof for nonsymmetric Hessenberg matrices.

    Source: §1 · pp. 2–3, §1.1 · p. 5

  • Method

    The paper regularizes shifts with random perturbations and proves that non-optimal forward-approximate Ritz values trigger early decoupling instead of undermining convergence.

    Source: §1.1 · pp. 3–4

  • Results

    The Part I strategy Shk,B converges rapidly in finite arithmetic with a polylogarithmic precision bound for matrices with controlled eigenvector condition number and minimum eigenvalue gap.

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

  • Takeaways & Limitations

    The framework turns forward instability into a dichotomy between stable Ritz-value shifts and rapid matrix decoupling, enabling a rigorous finite-arithmetic convergence guarantee.

    Source: §1.1 · p. 4

    The framework assumes controlled eigenvector conditioning and a positive minimum eigenvalue gap, and its small-eigenvalue solver relies on an auxiliary result rather than a previously established strong worst-case bound.

    Source: §1.1 · pp. 3, 5

Abstract

from arXiv · show

We develop a framework for proving rapid convergence of shifted QR algorithms which use Ritz values as shifts, in finite arithmetic. Our key contribution is a dichotomy result which addresses the known forward-instability issues surrounding the shifted QR iteration [Parlett and Le 1993]: we give a procedure which provably either computes a set of approximate Ritz values of a Hessenberg matrix with good forward stability properties, or leads to early decoupling of the matrix via a small number of QR steps. Using this framework, we show that the shifting strategy introduced in Part I of this series [Banks, Garza-Vargas, and Srivastava 2021] converges rapidly in finite arithmetic with a polylogarithmic bound on the number of bits of precision required, when invoked on matrices of controlled eigenvector condition number and minimum eigenvalue gap.

1 Introduction

The paper develops a finite-arithmetic framework for shifted QR with Ritz-value shifts, resolving forward-stability and Ritz-value computation issues through regularization and an optimality/early-decoupling dichotomy. Applied to Shk,B, the framework yields rapid convergence under controlled eigenvector conditioning and eigenvalue gaps, while exposing precision and implementation trade-offs.

1 Introduction

  • Forward stability is necessary because backward stability alone controls correctness after convergence but cannot bound iteration counts through rapid decay of Hessenberg subdiagonal entries.Forward instability arises when the shift polynomial p(H) is nearly singular, a situation that can occur before decoupling.Source: §1 · p. 2, §1.1 · p. 3

1.1 Results and Organization

  • The paper reduces approximate Ritz-value computation to forward eigenvalue approximation for the bottom-right k × k corner and uses SmallEig as a black-box solver for small matrices.SmallEig returns eigenvalues within absolute error β with probability at least 1 − φ, but the authors note that a strong precise worst-case bound was not previously available in the literature.Source: §1 · p. 3, §1.1 · pp. 4–5
  • Random shift regularization provides forward stability with high probability for implicit QR steps on Hessenberg matrices with bounded κV(H) and lower-bounded gap(H).Each shift is perturbed by an independent random complex Gaussian of appropriate size, while preserving forward-approximate Ritz values under sufficiently small perturbations.Source: §1.1 · pp. 3–4
  • If computed forward-approximate Ritz values are not θ-optimal, the dichotomy identifies a shift causing immediate early decoupling through a degree-k QR step.This converts failure of Ritz-value optimality into progress toward convergence rather than requiring every computed shift set to be optimal.Source: §1.1 · pp. 3–4
  • A Hessenberg Toeplitz example shows that backward approximations of H(k) eigenvalues need not yield O(1)-optimal Ritz values, even when the full matrix is close to normal.The example motivates requiring forward accuracy and distinguishes conditioning of H from conditioning of its trailing submatrix.Source: §1.1 · p. 4
  • Deflation must preserve eigenvector conditioning and eigenvalue gaps when passing to submatrices, and the complete algorithm combines this preservation with the shifting strategy after decoupling.The resulting framework is intended primarily for rigorous analysis and further engineering rather than as a directly competitive software implementation.Source: §1.1 · p. 5, §1.3 · p. 8
  • Theorem 1.4 gives a randomized finite-arithmetic ShiftedQR algorithm for Shk,B that returns eigenvalues of a δ-relative backward perturbation with high probability under controlled κV(H) and gap(H).The strategy uses k = O(log B log log B), where B bounds the eigenvector condition number and Γ bounds the minimum eigenvalue gap.Source: §1 · p. 2, §1.1 · p. 5

1.2 Related Work

  • The implementation uses k sequential degree-1 small-bulge QR steps instead of large-bulge chasing to avoid shift blurring, at the cost of increased precision roughly O(k log(n/δ)) bits.The authors identify reducing this cost from O(log^2(n/δ) log log(n/δ)) to O(log(n/δ)) as a central open problem.Source: §1.2 · p. 7, §1.3 · p. 8

2 Preliminaries

The preliminaries establish the finite-precision model, Hessenberg and spectral notation, approximate functional tools, and parameter settings used to analyze ShiftedQR.

2 Preliminaries

  • Finite arithmetic assumes relative error u for basic operations, while random shift perturbations are treated as exact because their finite-precision effect on failure probability is O(u/δ2).Source: §2 · pp. 8–9

2.1 Key Definitions and Lemmas from [BGVS22a]

  • Ritz values are eigenvalues of H(k), the bottom-right k × k corner, and also minimize the residual norm over monic degree-k polynomials.Source: §2.1 · p. 9
  • The analysis uses approximate functional calculus and a distribution Z_H on Spec(H) to relate polynomial behavior to eigenvalue and eigenvector structure.Source: §2.1 · p. 10
  • For θ-approximate Ritz values, stagnation of a shifted QR step implies spectral support near a shift and a nearby eigenvalue with aligned eigenvector structure.Source: §2.1 · p. 10

2.2 Reader Guide and Parameter Settings

  • ShiftedQR chooses shift degree k from the non-normality bound B, with k = O(log B log log B), and tracks controlled condition numbers, norms, and eigenvalue gaps.Source: §2.2 · p. 11
  • The paper uses absolute decoupling: H is ω-decoupled when one of its k bottom subdiagonal entries is below ω, and ω-unreduced when all exceed ω.Source: §2.2 · p. 11

3 Implicit QR: Implementation, Forward Stability, and Regularization

This section builds implicit QR from backward-stable degree-1 steps, derives forward-error bounds for higher-degree shifts, and regularizes shifts randomly to obtain forward stability with high probability.

3.2 Forward Stability of Higher Degree IQR

3.3 Shift Regularization

  • A sufficiently large random perturbation of any shifts makes a higher-degree implicit QR step forward stable with high probability.Source: §3 · p. 12, §3.3 · p. 17

3.1 Description and Backward Stability of IQR

  • The exact higher-degree implicit QR transformation satisfies a composition property: applying shifts sequentially equals the QR step for their product polynomial.Source: §3.1 · p. 13
  • The IQR implementation satisfies backward-stability guarantees, is νIQR(n)-stable with νIQR(n)=32n3/2, and uses at most 7n2 arithmetic operations.Source: §3.1 · p. 14
  • Higher-degree IQR is implemented by composing k degree-1 steps, with total cost TIQR(n, k) = 7kn2 arithmetic operations.Source: §3.1 · p. 15

3.3 Shift Regularization

  • Independent perturbations in disks of radius η2 keep all regularized shifts at least η1 from the spectrum with probability at least 1 − k(η1/η2)2.Source: §3.3 · p. 17

4 Finding Forward Stable Optimal Ritz Values (or Decoupling Early)

This section develops a dichotomy for approximate Ritz values: they are either θ-optimal or enable early decoupling, and implements it as the finite-arithmetic procedure RitzOrDecouple.

4.1 The Dichotomy in Exact Arithmetic

  • Theorem 4.1 shows that β-forward approximate Ritz values are either θ-optimal or contain a shift enabling decoupling in one degree-k QR step.The offending Ritz value is close to an eigenvalue of H whose right eigenvector has a large inner product with e_n.Source: §4.1 · pp. 18, 20
  • The dichotomy follows because nearby polynomial roots can produce a large norm discrepancy only when one perturbed root lies near an eigenvalue carrying significant spectral mass.The proof interpolates between the original and perturbed roots in batches and bounds the resulting expectation changes.Source: §4.1 · pp. 18–20

4.2 Finite Arithmetic Implementation of RitzOrDecouple

  • RitzOrDecouple first computes forward approximations with SmallEig, then tests θ-optimality and applies candidate shifts when optimality fails.Its input assumptions include an ω-unreduced Hessenberg matrix, a norm bound, and a minimum gap condition.Source: §4.2 · pp. 22–23
  • With probability at least 1 −φ, RitzOrDecouple returns either exact θ-optimal Ritz values in D(0, 1.1∥H∥) with unchanged H, or an ω-decoupled Hessenberg matrix.In the decoupling case, the output is IQR(H, (z −ˇr)k) for some ˇr ∈ˇR.Source: §4.2 · p. 23
  • The optimality test runs in O(k^2) arithmetic operations, while the decoupling branch has running time O(k^2n^2).The procedure makes one call to SmallEig, with additional implicit QR work depending on whether decoupling occurs.Source: §4.2 · pp. 22–24

5 Finite Arithmetic Analysis of One Iteration of Shk,B

This section extends the shifting strategy Shk,B to finite arithmetic by combining promising-shift search, forward-stable exceptional shifts, and potential-based acceptance tests.

Analysis of Find

  • Find uses a binary search guided by τ to produce an α-promising Ritz value from θ-approximate Ritz values, with runtime O(k log k · n^2).Its implementation recursively compares products associated with two partitions of the candidate set.Source: §5 · pp. 25–26

Analysis of Exc

  • Exc constructs a finite net of perturbed exceptional shifts and randomly translates it so the shifts are forward stable with high probability.The net is chosen around the initial promising shift, and the random translation bounds the chance that any shift approaches Spec(H).Source: §5 · pp. 27–30
  • For forward-stable shifts, Lemma 5.2 guarantees either a small subdiagonal entry or the finite-arithmetic potential bound needed for progress.This connects the exceptional-shift search to either decoupling or a certified reduction in ψ_k.Source: §5 · pp. 27, 30

Analysis of Shk,B

  • With probability at least 1 −φ, one iteration of Shk,B either ω-decouples H or reduces ψ_k(H) by the factor 1.002(1 −γ).The strategy first tries a promising Ritz shift, then searches exceptional shifts if that step stagnates.Source: §5 · pp. 31–32
  • The iteration’s runtime is the sum of Find, τ, and Exc costs plus the implicit QR tests over the exceptional-shift set.The stated bound is TSh(n,k,γ,B,α,θ) := TFind(n,k) + TTau(n,k) + TExc(n,k,0.999(1 −γ),(1 −γ),B,α,θ).Source: §5 · pp. 31–32

6 Finite Arithmetic Analysis of ShiftedQR

The full finite-arithmetic algorithm preserves the spectral conditions needed by the shifting strategy while recursively decoupling and deflating Hessenberg blocks.

6.1 Preservation of gap and κV

  • Deflation preserves or improves the eigenvalue gap and does not increase the eigenvector condition number of a diagonal block.This preservation is essential because the analysis of Shk,B assumes controlled κV and gap throughout recursion.Source: §6.1 · p. 33

6.2 The Full Algorithm

  • The algorithm outputs eigenvalues of a matrix within the requested backward-error tolerance, after reducing the problem to k × k or smaller diagonal blocks.The input/output contract states that the returned multiset corresponds to some eH with ∥eH − H∥ ≤ δ.Source: §6.2 · pp. 34–35
  • Theorem 6.3 guarantees finite-arithmetic correctness and bounds the recursive algorithm’s arithmetic cost and SmallEig calls under controlled norm, condition number, and gap assumptions.The failure analysis uses a union bound over calls to RitzOrDecouple, Shk,B, and SmallEig.Source: §6.2 · pp. 34, 38
  • ShiftedQR alternates RitzOrDecouple and Shk,B, then deflates ω-decoupled matrices into diagonal Hessenberg blocks and recurses on blocks larger than k × k.The analysis embeds these block operations into approximate unitary conjugations of the original matrix.Source: §6.2 · pp. 33–35
  • Each while-loop terminates after at most Ndec iterations, producing an ω-decoupled matrix at most ω-far from a unitary conjugate of its input.Every iteration either decouples or reduces the potential by a multiplicative factor 1.002(1 −γ).Source: §6.2 · pp. 36–37

A Deferred proofs from Section 3

These deferred proofs establish finite-arithmetic stability and cost bounds for implicit QR steps by tracking structured errors through Givens rotations.

Deferred proofs from Section 3

  • The IQR analysis represents the computed step as a unitary conjugation plus structured error matrices supported on a small number of rows.The proof defines the intermediate matrices and Givens rotations explicitly, then propagates their errors inductively.Source: A Deferred proofs from Section 3 · pp. 40–41
  • The computed shifted matrix satisfies a backward-error relation obtained by reapplying the stored rotations and bounding the accumulated perturbations.The resulting expression compares the computed output with the exact unitary conjugation of H − s.Source: A Deferred proofs from Section 3 · p. 41
  • A single IQR step uses at most 7n^2 arithmetic operations for n ≥ 2.The count includes forming the shifted matrix, applying Givens rotations, replaying them, and reapplying the shift.Source: A Deferred proofs from Section 3 · p. 41
  • For a sequence of shifts, the proof bounds the product error by inductively combining the single-step IQR estimates.The accumulation depends on ν_IQR(n)u and the number of shifts, under the assumption ν_IQR(n)u ≤ 1/4.Source: A Deferred proofs from Section 3 · pp. 41–42
Loading 2205.06810v1…