Expand description
§Chapter 12.6.2 — Shift-invert: eigsh_near over SupernodalLdl, eigs_near over Lu
§Purpose
The k eigenvalues nearest a shift σ. Krylov methods find the ends
of the spectrum quickly and the interior slowly; ARPACK’s mode 3 for the
standard problem runs them on (A − σI)⁻¹, whose largest eigenvalues
ν = 1/(λ − σ) are the λ nearest σ. The factorization comes from
xingo-sparse: the threshold LU (Lu<T>) for a general A, and the
supernodal LBLᵀ (SupernodalLdl<T, K>, Bunch–Kaufman pivoting,
no regularization) for a symmetric one — whose inertia counts, by
Sylvester’s law, the eigenvalues of A below σ: a check of
completeness that ARPACK does not offer (SymShiftInvert::count_below).
§Notation
A ∈ R^{n×n} sparse (CSC); σ the real shift; M = A − σI; ν the
eigenvalues of M⁻¹; In(M) = (n₊, n₋, n₀) its inertia.
§Algorithm SI (symmetric, eigsh_near)
SI1. [Check.] A square and structurally valid, entries and σ
finite; the arguments of crate::eigsh() are validated first.
SI2. [Form.] The lower triangle of M (entries a_ij, i ≥ j, of the
input — only the lower triangle is read — with σ subtracted on the
diagonal; an entry that becomes exactly zero is not stored, as the
CSC invariant requires, and the analysis adds the structural
diagonal).
SI3. [Factorize.] Analyze with the crate’s own AMD and factorize by the
LBLᵀ path of SupernodalLdl (no regularization: Regularization:: none() on an augmented form). That path checks the inertia against
the form’s (KktForm::Augmented { n_primal, n_dual } expects
(n_dual, n_primal, 0)), and the inertia of M is not known in
advance: the first attempt declares (n, 0, 0) (right whenever
σ is below the spectrum); on WrongInertia { found } with found.zero = 0 the analysis and the factorization are repeated with
n_primal = found.negative — at most two factorizations. A zero
pivot (found.zero > 0, or ZeroPivot) means σ is numerically an
eigenvalue: StatlaError::Kkt.
SI4. [Count.] count_below = n₋, the eigenvalues of A strictly below
σ (Sylvester; exact for the computed factorization, i.e. for a
matrix within the backward error of LBLᵀ from M).
SI5. [Iterate.] crate::eigsh() with LM on x ↦ M⁻¹x, each
application by Algorithm R below (two solves and one product with
M).
SI6. [Map back.] λ = σ + 1/ν; the order (largest |ν| first) is
nearest σ first; the eigenvectors are those of M⁻¹.
§Algorithm SG (general, eigs_near)
SG1–SG2 as SI1–SI2 on the whole of M. SG3: Lu<T> with
LuOptions::for_scalar::<T>() (the defaults of xingo-sparse; M
is the “basis” whose columns are those of M); singular is
StatlaError::Lu. SG5: crate::eigs() with LM on x ↦ M⁻¹x
(ftran: row-indexed in, column-indexed out; Algorithm R). SG6: λ = σ + 1/ν
computed by complex division. 1/ν conjugates the imaginary part’s
sign, so a pair ν, ν̄ (+i first) maps to λ̄, λ: the two values,
and the imaginary parts of their vectors, are swapped back to keep the
+i member first; a lone k-th member is replaced by its conjugate.
§Algorithm R (one step of iterative refinement per application)
Task L3.4, second round (answer to question Q-L34-4). Both operators
apply x ↦ M⁻¹x as
R1. [Solve.] y ← F⁻¹x with the factorization F ≈ M (LU ftran, or
the LBLᵀ solve).
R2. [Residual.] r ← x − M y, in the scalar T, with the stored M
(the whole A − σI for the LU; its lower triangle, applied
symmetrically, for the LBLᵀ).
R3. [Correct.] y ← y + F⁻¹r.
What it guarantees. Without R2–R3 the computed y solves (M + δM) y = x with ‖δM‖ the backward error of the factorization, which for a
threshold LU (rel_pivot_tol = 0.01) or a Bunch–Kaufman LBLᵀ carries
the element growth, γ·u·‖M‖ with γ up to hundreds — and that, not
the convergence tolerance, bounded the residual on A (measured 114·ncv ·u‖A‖ for eigs_near, 4.75 for eigsh_near, task L3.4 first round).
One step of refinement in the working precision makes the solve
backward stable with ‖δM‖ = O(n_row · u · ‖M‖) (componentwise, the row
counts of M), provided γ·κ(M)·u is well below one (Skeel 1980;
Higham, Accuracy and Stability, ch. 12: fixed-precision refinement
improves the backward error, not the forward one). That is what the
residual on A needs: for a converged pair, ‖A y − λ y‖ = ‖M y − y/ν‖ ≤ ‖M‖·ρ_ν/|ν| + ‖δM‖, so a residual in T suffices; a residual in higher
precision would improve the forward error of each solve, which the
eigenvalue problem does not need (the error along the wanted eigenvector
is harmless, as in ARPACK’s mode 3). It does not remove the
dependence on κ(M): for σ within γ·u·‖M‖ of an eigenvalue one step
may not suffice (and the factorization would usually have failed with
a zero pivot). Measured (l34-tables.md): with R2–R3 the residual on
A satisfies the criterion of eigsh/eigs, ≤ (τ + c_K·ncv·u)‖A‖, on
every fixture.
Cost. Per application one more solve and one sparse product with M
(2·nnz(M) flops; the solves dominate), and the n-vectors r, d
kept in the operator; the stored M doubles the matrix memory.
§Invariants
(I1) count_below + n₀ + n₊ = n with n₀ = 0 for every operator built.
(I2) The applications solve M y = x with backward error η = ‖x − My‖_∞/(‖M‖_∞‖y‖_∞) = O(u) after Algorithm R (measured ≤ 0.73u
on the fixtures, against up to 526u without it; tested ≤ 2u by
tests/arpack.rs).
(I4) Algorithm R runs on every application (one refinement step, never
more, never skipped: the results are reproducible bit for bit).
(I3) eigsh_near/eigs_near return exactly the values σ + 1/ν of the
pairs eigsh/eigs returned on M⁻¹, in that order (up to the swap
of SG6 inside a pair).
§References
Lehoucq, Sorensen & Yang, ARPACK Users’ Guide (1998), mode 3;
Parlett, The Symmetric Eigenvalue Problem (1998), §3.3 (Sylvester’s
inertia and spectrum slicing); Ericsson & Ruhe, “The spectral
transformation Lanczos method”, Math. Comp. 35 (1980); Chapters 5.15–5.16
of xingo-sparse (LBLᵀ, Bunch–Kaufman). Cited from memory.
Structs§
- Shift
Invert x ↦ (A − σI)⁻¹ xfor a square sparseA, by the threshold LU ofxingo-sparse(Lu<T>over the columns ofA − σI, factorized once), with one step of iterative refinement per application (Algorithm R: two solves and one product withA − σI, which the operator keeps). The operator ofeigs_near(Algorithm SG of Chapter 12.6.2).- SymShift
Invert x ↦ (A − σI)⁻¹ xfor a symmetric sparseA(lower triangle read), bySupernodalLdl<T, K>with no regularization; the inertia ofA − σIis kept: by Sylvester’s law it counts the eigenvalues belowσ(SymShiftInvert::count_below) — a check ARPACK does not offer. Each application refines once (Algorithm R: two solves and one product with the kept lower triangle ofA − σI). The operator ofeigsh_near(Algorithm SI of Chapter 12.6.2).
Functions§
- check_
apply 🔒 - The length check of an application of a shift-invert operator.
- check_
input 🔒 - SI1/SG1 (after the structure check): square, finite entries and shift.
- eigs_
near - The
keigenvalues of the generalAnearest the real shiftσ, byeigs()onShiftInvert(LuOptions::for_scalar::<T>()), mapped back byλ = σ + 1/ν, nearest first; conjugate pairs keep the+imember first. - eigsh_
near - The
keigenvalues of the symmetricAnearestσ:eigsh()withLargestMagnitudeonSymShiftInvert, mapped back byλ = σ + 1/ν(ARPACK mode 3 for the standard problem), nearest first. Returns alsoSymShiftInvert::count_below. Only the lower triangle ofais read. - idx32 🔒
jas au32index (a validCscMatrixhas dimensions≤ u32::MAX, checked bycheck_invariantsbefore any use).- shifted 🔒
- SI2/SG2:
A − σI, the whole matrix or its lower triangle. - sub_
product 🔒 - Step R2:
r ← r − M y, withmthe wholeMor (symmetric) its lower triangle applied as the symmetric matrix it stands for.