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}