Skip to main content

Module shift_invert

Module shift_invert 

Source
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§

ShiftInvert
x ↦ (A − σI)⁻¹ x for a square sparse A, by the threshold LU of xingo-sparse (Lu<T> over the columns of A − σI, factorized once), with one step of iterative refinement per application (Algorithm R: two solves and one product with A − σI, which the operator keeps). The operator of eigs_near (Algorithm SG of Chapter 12.6.2).
SymShiftInvert
x ↦ (A − σI)⁻¹ x for a symmetric sparse A (lower triangle read), by SupernodalLdl<T, K> with no regularization; the inertia of A − σI is 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 of A − σI). The operator of eigsh_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 k eigenvalues of the general A nearest the real shift σ, by eigs() on ShiftInvert (LuOptions::for_scalar::<T>()), mapped back by λ = σ + 1/ν, nearest first; conjugate pairs keep the +i member first.
eigsh_near
The k eigenvalues of the symmetric A nearest σ: eigsh() with LargestMagnitude on SymShiftInvert, mapped back by λ = σ + 1/ν (ARPACK mode 3 for the standard problem), nearest first. Returns also SymShiftInvert::count_below. Only the lower triangle of a is read.
idx32 🔒
j as a u32 index (a valid CscMatrix has dimensions ≤ u32::MAX, checked by check_invariants before any use).
shifted 🔒
SI2/SG2: A − σI, the whole matrix or its lower triangle.
sub_product 🔒
Step R2: r ← r − M y, with m the whole M or (symmetric) its lower triangle applied as the symmetric matrix it stands for.