Skip to main content

xingo_statla/
krylov.rs

1//! # Chapter 12.0.7 — Krylov machinery shared by the restarted drivers
2//!
3//! ## Purpose
4//! [`crate::svds()`] (Chapter 12.5) and [`crate::eigsh()`]/[`crate::eigs()`] (12.6)
5//! grow orthonormal bases one vector at a time, restart them keeping a few
6//! Ritz vectors, and lock what has converged. The three pieces they share
7//! live here, so that the L3.4 engines reuse them unchanged: the expansion
8//! step with full DGKS reorthogonalization and its breakdown rule, the
9//! choice of the restart dimension, and the counters.
10//!
11//! ## Notation
12//! `V ∈ T^{r×j}` the current basis (the first `j` columns of a preallocated
13//! column-major array with `r` rows), orthonormal; `w ∈ T^r` the candidate
14//! after the recurrence terms were subtracted; `η` the DGKS threshold;
15//! `floor` the breakdown threshold `ε_T·σ̃_est` (an estimate of `‖A‖`).
16//!
17//! ## Algorithm E (expansion step)
18//! E1. \[Reorthogonalize.\] `w ← (I − VVᵀ)w` by Algorithm D of Chapter
19//!     12.0.4 (classical Gram–Schmidt against **all** of `V`, a second pass
20//!     when `‖w‖` fell below `η` times its value, never a third); count the
21//!     second passes.
22//! E2. \[Breakdown?\] `ν ← ‖w‖`. If `ν > floor`: `v_{j+1} ← w/ν`, return `ν`.
23//! E3. \[Replace.\] Otherwise the Krylov space is (numerically) invariant:
24//!     if `j = r` there is no room — `v_{j+1} ← 0`, return `0` (the callers
25//!     only reach this at the last step, where a zero coupling makes every
26//!     residual zero). Else draw `w` from the seed's stream (Algorithm G),
27//!     orthogonalize it against `V` twice (both passes unconditionally),
28//!     `v_{j+1} ← w/‖w‖`, return `0`: the coupling coefficient is set to
29//!     zero, a perturbation of `A` of norm `≤ floor` (recorded as backward
30//!     error), and the iteration continues in the orthogonal complement.
31//!
32//! ## Algorithm K (restart dimension)
33//! Given `k` wanted, `ncv` the basis size, `n_conv` the wanted values that
34//! have converged and `n_lock` the locked ones: `k′ ← k + min(⌊(ncv −
35//! k)/2⌋, n_conv)` (ARPACK's rule, `dsaup2`: keep more when more has
36//! converged, to protect the unconverged), then `k′ ← max(k′, n_lock + 1)`
37//! (at least one active vector) and `k′ ← min(k′, ncv − 1)` (room for the
38//! residual vector).
39//!
40//! ## Invariants
41//! (E1) After Algorithm E, `v_{j+1}` is a unit vector (or zero in the
42//!      no-room case) and `‖Vᵀv_{j+1}‖ ≤ c·j·u` — the (G1)/(K1) bound of
43//!      the drivers, measured there.
44//! (E2) The coefficient returned is `0` exactly when the step broke down.
45//!
46//! ## References
47//! Daniel, Gragg, Kaufman & Stewart (1976) (DGKS); Lehoucq, Sorensen &
48//! Yang, *ARPACK Users' Guide* (1998), `dsaup2`/`dnaup2` (the `nev′` rule);
49//! Wu & Simon (2000) (thick restart). Cited from memory.
50
51use xingo_sparse::Real;
52
53use crate::random::Rng;
54use crate::real::lt;
55use crate::small::{norm2, orthogonalize_against, orthogonalize_prefix};
56
57/// Algorithm E with the Gram–Schmidt coefficients of step E1 accumulated
58/// into `h` (length `≥ ncols`, added to): the Arnoldi step of Chapter 12.6.
59/// On breakdown the coefficients of the replacement vector are *not*
60/// recorded (it is not `A v_j`). Otherwise as [`expand`].
61#[allow(clippy::too_many_arguments)]
62pub(crate) fn expand_arnoldi<T: Real>(
63    basis: &[T],
64    rows: usize,
65    ncols: usize,
66    w: &mut [T],
67    h: &mut [T],
68    eta: T,
69    floor: T,
70    rng: &mut Rng,
71    reorth: &mut usize,
72) -> T {
73    // E1.
74    let (nu, passes) = orthogonalize_prefix(basis, rows, ncols, w, eta, Some(h));
75    if passes == 2 {
76        *reorth += 1;
77    }
78    replace_or_normalize(basis, rows, ncols, w, nu, floor, rng)
79}
80
81/// Steps E2–E3 on an orthogonalized `w` of norm `nu`.
82fn replace_or_normalize<T: Real>(
83    basis: &[T],
84    rows: usize,
85    ncols: usize,
86    w: &mut [T],
87    nu: T,
88    floor: T,
89    rng: &mut Rng,
90) -> T {
91    // E2.
92    if lt(floor, nu) {
93        for v in w.iter_mut() {
94            *v = *v / nu;
95        }
96        return nu;
97    }
98    // E3.
99    if ncols >= rows {
100        w.fill(T::ZERO);
101        return T::ZERO;
102    }
103    for v in w.iter_mut() {
104        *v = T::from_f64(rng.gaussian());
105    }
106    orthogonalize_against(basis, rows, ncols, w, T::ONE);
107    orthogonalize_against(basis, rows, ncols, w, T::ONE);
108    let nr = norm2(w);
109    for v in w.iter_mut() {
110        *v = *v / nr;
111    }
112    T::ZERO
113}
114
115/// Algorithm E on the first `ncols` columns of `basis` (`rows` rows);
116/// on return `w` holds `v_{ncols+1}`. Returns the coupling coefficient
117/// (`0` on breakdown). `reorth` counts the second DGKS passes.
118#[allow(clippy::too_many_arguments)]
119pub(crate) fn expand<T: Real>(
120    basis: &[T],
121    rows: usize,
122    ncols: usize,
123    w: &mut [T],
124    eta: T,
125    floor: T,
126    rng: &mut Rng,
127    reorth: &mut usize,
128) -> T {
129    // E1.
130    let (nu, passes) = orthogonalize_against(basis, rows, ncols, w, eta);
131    if passes == 2 {
132        *reorth += 1;
133    }
134    replace_or_normalize(basis, rows, ncols, w, nu, floor, rng)
135}
136
137/// Algorithm K.
138pub(crate) fn kept_dimension(k: usize, ncv: usize, n_conv: usize, n_lock: usize) -> usize {
139    let kp = k + ((ncv - k) / 2).min(n_conv);
140    kp.max(n_lock + 1).min(ncv - 1)
141}
142
143#[cfg(test)]
144#[allow(clippy::float_cmp)]
145mod tests {
146    use super::*;
147
148    #[test]
149    fn expansion_normalizes_or_replaces() {
150        // Basis e_0, e_1 in R^3.
151        let basis = [1.0, 0.0, 0.0, 0.0, 1.0, 0.0];
152        let mut rng = Rng::new(0);
153        let mut c = 0;
154        let mut w = [0.3, -0.2, 2.0];
155        let nu = expand(&basis, 3, 2, &mut w, 0.7, 1e-12, &mut rng, &mut c);
156        assert_eq!((nu, w), (2.0, [0.0, 0.0, 1.0]));
157        assert_eq!(c, 0, "no second pass: ‖w‖ fell only from 2.03 to 2");
158        // In the span: breakdown, a unit vector orthogonal to the basis.
159        let mut w = [0.3, -0.2, 1e-20];
160        let nu = expand(&basis, 3, 2, &mut w, 0.7, 1e-12, &mut rng, &mut c);
161        assert_eq!((nu, c), (0.0, 1));
162        assert!((w[2].abs() - 1.0).abs() < 1e-15 && w[0].abs() < 1e-15 && w[1].abs() < 1e-15);
163        // No room: zero vector.
164        let full = [1.0, 0.0, 0.0, 1.0];
165        let mut w = [1e-30, 0.0];
166        assert_eq!(
167            expand(&full, 2, 2, &mut w, 0.7, 1e-12, &mut rng, &mut c),
168            0.0
169        );
170        assert_eq!(w, [0.0, 0.0]);
171    }
172
173    #[test]
174    fn restart_dimension_follows_the_arpack_rule() {
175        assert_eq!(kept_dimension(5, 20, 0, 0), 5);
176        assert_eq!(kept_dimension(5, 20, 3, 0), 8);
177        assert_eq!(kept_dimension(5, 20, 4, 4), 9);
178        assert_eq!(kept_dimension(5, 20, 100, 0), 12);
179        assert_eq!(kept_dimension(5, 6, 0, 5), 5);
180        assert_eq!(kept_dimension(1, 2, 0, 0), 1);
181    }
182}