Skip to main content

Module eigs

Module eigs 

Source
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 k values are returned, as scipy does: when the k-th value is the first member of a conjugate pair, its conjugate is omitted (question Q-L34-1).
  • BE returns 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§

ActiveSchur 🔒
The result of KS3 on the active block.
Blk 🔒
One block of T at 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 k values: the conjugate of a k-th value with positive imaginary part is omitted, as scipy does).
EigsOptions
Options of eigs() and eigsh(). Defaults are scipy’s (scipy.sparse.linalg.eigs/eigsh) where it has one.
EigsStats
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, im with 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 through xingo-ffi unchanged. eigsh() accepts LM SM LA SA BE; eigs() accepts LM SM LR SR LI SI; any other combination is StatlaError::InvalidArgument.

Constants§

C_K 🔒
The constant c_K of invariants (K1)–(K2) and of the residual guarantee (measured in task L3.4, with a margin).

Functions§

before 🔒
a before b in the order of which (strict), on representatives with im ≥ 0.
eigs
k eigenpairs of a general real operator.
eigsh
k eigenpairs of a symmetric operator (the caller asserts the symmetry; it is not checked).
eps23 🔒
ε_T^{2/3} by Newton’s iteration on y³ = ε² (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 by tie_break, then the input order (locked blocks come first).
run 🔒
Algorithm KS (sym selects the symmetric small solver of KS3).
sym_result 🔒
tie_break 🔒
The tie-break of which: ARPACK’s dngets pre-sorts by this key before the stable sort by which (LM↔LR, SM↔SR, LI→LM, SI→SM), so that equal keys (a spectrum of real values under LI, ±λ under LM) 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).