Expand description
§Chapter 12.0.7 — Krylov machinery shared by the restarted drivers
§Purpose
crate::svds() (Chapter 12.5) and crate::eigsh()/crate::eigs() (12.6)
grow orthonormal bases one vector at a time, restart them keeping a few
Ritz vectors, and lock what has converged. The three pieces they share
live here, so that the L3.4 engines reuse them unchanged: the expansion
step with full DGKS reorthogonalization and its breakdown rule, the
choice of the restart dimension, and the counters.
§Notation
V ∈ T^{r×j} the current basis (the first j columns of a preallocated
column-major array with r rows), orthonormal; w ∈ T^r the candidate
after the recurrence terms were subtracted; η the DGKS threshold;
floor the breakdown threshold ε_T·σ̃_est (an estimate of ‖A‖).
§Algorithm E (expansion step)
E1. [Reorthogonalize.] w ← (I − VVᵀ)w by Algorithm D of Chapter
12.0.4 (classical Gram–Schmidt against all of V, a second pass
when ‖w‖ fell below η times its value, never a third); count the
second passes.
E2. [Breakdown?] ν ← ‖w‖. If ν > floor: v_{j+1} ← w/ν, return ν.
E3. [Replace.] Otherwise the Krylov space is (numerically) invariant:
if j = r there is no room — v_{j+1} ← 0, return 0 (the callers
only reach this at the last step, where a zero coupling makes every
residual zero). Else draw w from the seed’s stream (Algorithm G),
orthogonalize it against V twice (both passes unconditionally),
v_{j+1} ← w/‖w‖, return 0: the coupling coefficient is set to
zero, a perturbation of A of norm ≤ floor (recorded as backward
error), and the iteration continues in the orthogonal complement.
§Algorithm K (restart dimension)
Given k wanted, ncv the basis size, n_conv the wanted values that
have converged and n_lock the locked ones: k′ ← k + min(⌊(ncv − k)/2⌋, n_conv) (ARPACK’s rule, dsaup2: keep more when more has
converged, to protect the unconverged), then k′ ← max(k′, n_lock + 1)
(at least one active vector) and k′ ← min(k′, ncv − 1) (room for the
residual vector).
§Invariants
(E1) After Algorithm E, v_{j+1} is a unit vector (or zero in the
no-room case) and ‖Vᵀv_{j+1}‖ ≤ c·j·u — the (G1)/(K1) bound of
the drivers, measured there.
(E2) The coefficient returned is 0 exactly when the step broke down.
§References
Daniel, Gragg, Kaufman & Stewart (1976) (DGKS); Lehoucq, Sorensen &
Yang, ARPACK Users’ Guide (1998), dsaup2/dnaup2 (the nev′ rule);
Wu & Simon (2000) (thick restart). Cited from memory.
Functions§
- expand 🔒
- Algorithm E on the first
ncolscolumns ofbasis(rowsrows); on returnwholdsv_{ncols+1}. Returns the coupling coefficient (0on breakdown).reorthcounts the second DGKS passes. - expand_
arnoldi 🔒 - Algorithm E with the Gram–Schmidt coefficients of step E1 accumulated
into
h(length≥ ncols, added to): the Arnoldi step of Chapter 12.6. On breakdown the coefficients of the replacement vector are not recorded (it is notA v_j). Otherwise asexpand. - kept_
dimension 🔒 - Algorithm K.
- replace_
or_ 🔒normalize - Steps E2–E3 on an orthogonalized
wof normnu.