Expand description
§Chapter 12.6 — eigsh and eigs: Krylov–Schur restarted Lanczos and Arnoldi with ARPACK’s contract
§Purpose
k eigenpairs at one end of the spectrum of a large sparse or implicit
operator. eigsh() (symmetric) and eigs() (general real) take
ARPACK’s vocabulary — the two-letter which codes, ncv, the relative
convergence test, scipy’s defaults — and restart by the Krylov–Schur
method of Stewart (2001) instead of ARPACK’s implicit QR shifts
(decision S7 of D-0127): with exact shifts both keep the same subspace,
and in Schur form locking and purging are deletions of rows and columns.
§Notation
A ∈ R^{n×n} the operator; m = ncv; V = [v_1 … v_{m+1}] ∈ T^{n×(m+1)}
orthonormal; H̄ ∈ T^{(m+1)×m} with rows 0..m the projected H and row
m the coupling row bᵀ. The Krylov decomposition kept throughout
is
A V_j = V_j H_j + v_{j+1} b_jᵀ (KS)with b_j = β_j e_j after an Arnoldi step and a full vector after a
restart. The first n_L columns are locked: their part of b is
zero and H = [S_LL H_LA; 0 H_AA] is block upper triangular, so the
eigenvalues of H are those of S_LL (quasi-triangular, fixed) and of
the active block H_AA. In the symmetric case H_LA = 0 and S_LL
is diagonal. τ is the tolerance (EigsOptions::tol, 0 meaning
ε_T), ε^{2/3} ARPACK’s floor of the test, ‖A‖_est = max_j ‖A v_j‖.
A Ritz pair (θ, y = V z) of H has residual ‖A y − θ y‖ = |bᵀ z| by
(KS) (‖z‖ = 1).
§Algorithm KS (Krylov–Schur, one engine for both drivers)
KS1. [Start.] v_1 ← v0/‖v0‖ (v0 from the options or n Gaussian
deviates of the seed’s stream, Algorithm G); j ← 0; n_L ← 0.
KS2. [Expand.] For j, …, m − 1: w ← A v_{j+1} (checked finite);
‖A‖_est ← max(‖A‖_est, ‖w‖); Gram–Schmidt against all of
V_{j+1} with a DGKS second pass, the coefficients of both passes
forming column j of H; β ← ‖w‖; if β ≤ ε_T‖A‖_est, an
invariant subspace: v_{j+2} is drawn from the seed’s stream and
orthogonalized, β ← 0 (Algorithm E of Chapter 12.0.7). h_{j+1,j} ← β. In eigsh (KS2′) the strict upper part of the new column is
then overwritten by the mirror of its row (β_{j−1}, or the
arrowhead b after a restart), so that H is exactly symmetric and
the tiny couplings of converged Ritz vectors stay tiny: the
Gram–Schmidt coefficients there are those couplings plus rounding
O(ε‖A‖), which only orthogonalize w (as in Lanczos, where they
are not stored).
KS3. [Schur.] Decompose the active block H_AA = Z_A T_A Z_Aᵀ: in
eigsh, T_A diagonal by the Jacobi method of the symmetrized
block (Algorithm SJ of 12.6.1); in eigs, the standardized real
Schur form by Hessenberg reduction and Francis double-shift QR
(HR + FQ). Then b_A ← b_Aᵀ Z_A, H_LA ← H_LA Z_A.
KS4. [Ritz.] The eigenvalues θ of the locked blocks and of T_A;
for an active block the eigenvector x of T_A (Algorithm EV) gives
the estimate ρ = |b_Aᵀ x|/‖x‖ (≥ the true one: the locked
components of the eigenvector of H are left out). The candidates
are ordered by which (a conjugate pair counts as two values,
adjacent, +i first; BE alternates the high and the low end,
high first; ties are broken by ARPACK’s secondary key — LM↔LR,
SM↔SR, LI→LM, SI→SM — then by position); the
wanted are the first k.
KS5. [Test.] A wanted value is converged when it is locked, or when
ρ ≤ τ·max(ε^{2/3}, |θ|) (ARPACK’s test, |θ| the modulus). If all
k are converged, go to KS8; if the restart limit is reached,
StatlaError::NoConvergence (or KS8 with the converged ones when
allow_partial).
KS6. [Reorder and lock.] k′ ← Algorithm K of Chapter 12.0.7 (n_conv the
converged wanted). Reorder T_A (Algorithm RO, the rotations
accumulated into Z_A, b_A recomputed) so that the converged
wanted lead, then the other wanted, then the rest, each group in
which order. Lock the leading active blocks, in order, while
they are converged wanted and their entries of b_A satisfy the
test of KS5 (for a symmetric T_A that is the estimate itself):
their entries of b become 0 — a perturbation of A of norm ≤ τ·max(ε^{2/3}, |θ|) — and their vectors are never rotated again.
KS7. [Truncate (purge).] Round k′ so that no 2 × 2 block is split
(up if there is room, else down), keep k′ ≥ n_L. V ← [V_L, V_A Z_A[:, :k′−n_L], v_{m+1}], H ← [S_LL, H_LA Z_A; 0, T_A] restricted
to k′, coupling row (0, b_A[:k′−n_L]) with the locked entries
zeroed: the unwanted Ritz values beyond k′ (converged or not) are
purged with their vectors. Count a restart; j ← k′; go to KS2.
KS7′. [Re-orthonormalize.] One Gram–Schmidt sweep (DGKS) of the new
active columns and of the residual vector against the columns before
them, locked ones untouched. V ← V Z_A in floating point loses
O(u) of orthogonality per restart, and the loss accumulates
(measured: 1.9·10⁻¹⁴ = 85u after 30 restarts at m = 20, against
≤ 4u with the sweep); the sweep perturbs (KS) by the loss it
removes, O(m u ‖A‖).
KS8. [Vectors.] For each wanted value the eigenvector x of the whole
quasi-triangular T = [S_LL, H_LA Z_A; 0, T_A] (Algorithm EV), y ← V blockdiag(I, Z_A) x, normalized to unit 2-norm in Cⁿ with its
largest entry real and positive (the conjugate for the −i member).
Algorithm L of the contract (thick-restart Lanczos, Wu & Simon 2000)
is Algorithm KS with a symmetric T_A: after a restart H is
diag(θ) plus the arrowhead b (row k′) and its mirror (column k′,
the Gram–Schmidt coefficients of the first new step), and the reordering
is a permutation. Both drivers therefore share one engine (two Krylov
engines in the crate instead of three: this and the bidiagonalization
of 12.5).
Reorthogonalization policy: full (KS2 against all of V, locked
vectors included), at most two classical Gram–Schmidt passes — the
policy of 12.5. Cost per step: one application plus ≈ 4nj flops; per
restart O(n m k′ + m³).
§Invariants
(K1) ‖V_jᵀV_j − I‖ ≤ c_K · j · u — debug-asserted after every restart
(c_K = C_K).
(K2) ‖A V_j − V_j H_j − v_{j+1} b_jᵀ‖ ≤ c_K · j · u · ‖A‖_est after every
expansion — computed by the unit tests (paranoid runs; it costs j
extra applications).
(K3) After a restart H̄ is zero outside [S_LL H_LA; 0 T_A] (top k′
rows) and the coupling row k′, whose locked entries are zero;
T_A is quasi-triangular (diagonal in eigsh) — debug-asserted.
(K4) Every returned pair passed the test of KS5 at the moment it was
locked or returned; locked columns of V are never modified again.
§Guarantee
A returned pair (θ, y) has, in exact arithmetic on the computed
decomposition, ‖A y − θ y‖ ≤ ρ + Σ_locked |b_dropped|·|x_L|, each term
≤ τ·max(ε^{2/3}, |θ|); rounding adds c_K·m·u·‖A‖_est by (K1)–(K2).
Hence the acceptance form ‖A y − θ y‖ ≤ (τ + c_K·m·u)·‖A‖ (when ‖A‖ ≥ ε^{2/3}). For symmetric A this bounds the distance of θ to the
spectrum (Parlett, Thm. 4.5.1); for a general A the eigenvalue error
is that times its condition number.
The constant c_K = C_K = 8 (measured in task L3.4, l34-tables.md):
the largest recomputed (‖r‖/‖A‖ − τ)/(m u) over the Matrix Market
fixtures was 2.44 in f64 (margin 3.3), (K2) at most 1.8, (K1)
debug-asserted with c_K in every test run. In double-double, whose
operations round to a few u (Chapter 11 of xingo-extprec), (K2)
reached 7.5 and the residual 19.4: its smoke tests use 64
(question Q-L34-7).
§Acceptance (L3.4, S9; tests/eigs.rs)
On Matrix Market matrices the k wanted eigenvalues agree with
scipy.sparse.linalg.eigsh/eigs (ARPACK; fixtures committed) to
1e-10 relative where the gap to the rest of the spectrum is ≥ 10⁻⁶‖A‖, and every pair has ‖Ay − θy‖ ≤ (τ + c_K·m·u)‖A‖ (with τ = 0 the literal τ‖A‖ is below the rounding of the residual itself; see
question Q-L34-2).
§Divergences from the references
- Restart by Krylov–Schur, not implicit QR (S7). Results are compared with ARPACK, not traces.
- The symmetric small solver is cyclic Jacobi, not tridiagonal QL (the
projected matrix after a restart is an arrowhead, not tridiagonal; and
Jacobi gives orthogonal eigenvectors to
O(ε)in every case). - Exactly
kvalues are returned, as scipy does: when thek-th value is the first member of a conjugate pair, its conjugate is omitted (question Q-L34-1). BEreturns the values in its own wanted order (high, low, high, …).
§References
Stewart, “A Krylov–Schur algorithm for large eigenproblems”, SIMAX 23
(2001); Wu & Simon, “Thick-restart Lanczos method for large symmetric
eigenvalue problems”, SIMAX 22 (2000); Lehoucq, Sorensen & Yang, ARPACK
Users’ Guide, SIAM (1998) (dsaupd/dnaupd: which, ncv, the test
‖r‖ ≤ tol·max(ε^{2/3}, |θ|), nev′); Sorensen, SIMAX 13 (1992);
Parlett, The Symmetric Eigenvalue Problem (1998); Daniel, Gragg,
Kaufman & Stewart (1976). Cited from memory.
Structs§
- Active
Schur 🔒 - The result of KS3 on the active block.
- Blk 🔒
- One block of
Tat the time of a test. - Complex
- A pair
re + i·im(eigenvalues of a real nonsymmetric operator). No arithmetic: a value type for results, not a complex scalar (complex matrices are out of scope). - Eigen
- Eigenpairs of a real nonsymmetric operator, most wanted first; complex
conjugate pairs are adjacent, positive imaginary part first (exactly
kvalues: the conjugate of ak-th value with positive imaginary part is omitted, as scipy does). - Eigs
Options - Options of
eigs()andeigsh(). Defaults are scipy’s (scipy.sparse.linalg.eigs/eigsh) where it has one. - Eigs
Stats - Work counters of the Krylov drivers.
- Engine 🔒
- The state of Algorithm KS.
- Params 🔒
- The validated parameters of one run.
- Raw 🔒
- The raw result of Algorithm KS: values (in wanted order,
imwith its sign) and the complex vectors. - SymEigen
- Symmetric eigenpairs, most wanted first (in the order of
which).
Enums§
- Which
- Which part of the spectrum, with ARPACK’s two-letter codes
(
Which::from_arpack) so that R and Python pass their strings throughxingo-ffiunchanged.eigsh()acceptsLM SM LA SA BE;eigs()acceptsLM SM LR SR LI SI; any other combination isStatlaError::InvalidArgument.
Constants§
- C_K 🔒
- The constant
c_Kof invariants (K1)–(K2) and of the residual guarantee (measured in task L3.4, with a margin).
Functions§
- before 🔒
abeforebin the order ofwhich(strict), on representatives withim ≥ 0.- eigs
keigenpairs of a general real operator.- eigsh
keigenpairs of a symmetric operator (the caller asserts the symmetry; it is not checked).- eps23 🔒
ε_T^{2/3}by Newton’s iteration ony³ = ε²(only+ − · /, a fixed number of steps: the same bits everywhere).- gen_
result 🔒 - invalid 🔒
- passes 🔒
- The test of KS5 for a value of modulus
abs. - rank_
blocks 🔒 - KS4: the order of the blocks with values
vals(representatives), most wanted first; ties bytie_break, then the input order (locked blocks come first). - run 🔒
- Algorithm KS (
symselects the symmetric small solver of KS3). - sym_
result 🔒 - tie_
break 🔒 - The tie-break of
which: ARPACK’sdngetspre-sorts by this key before the stable sort bywhich(LM↔LR,SM↔SR,LI→LM,SI→SM), so that equal keys (a spectrum of real values underLI,±λunderLM) are resolved the same way at every restart. - validate 🔒
- Check the arguments (in the order of the error conventions, 12.0.1).
- validate_
for 🔒 - The argument checks of
eigsh()/eigs(), for the shift-invert drivers (which validate before factorizing).