Skip to main content

Module krylov

Module krylov 

Source
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 ncols columns of basis (rows rows); on return w holds v_{ncols+1}. Returns the coupling coefficient (0 on breakdown). reorth counts 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 not A v_j). Otherwise as expand.
kept_dimension 🔒
Algorithm K.
replace_or_normalize 🔒
Steps E2–E3 on an orthogonalized w of norm nu.