xingo_statla/svds.rs
1//! # Chapter 12.5 — Truncated SVD by Golub–Kahan–Lanczos bidiagonalization with thick restart
2//!
3//! ## Purpose
4//! *The leading `k` singular triplets of an operator, each value accurate
5//! to `ε σ_1`.* [`svds()`] is a Krylov engine of its own (decision S2 of
6//! D-0127), not an eigensolver on `AᵀA`: it never squares the condition, so
7//! every singular value comes out with an *absolute* error of order `ε σ_1`
8//! — where scipy's ARPACK-on-the-normal-operator route gives `ε σ_1²/σ_i`.
9//!
10//! ## Notation
11//! `A ∈ T^{m×n}`; `P_j = [p_1 … p_j] ∈ T^{n×j}`, `U_j = [u_1 … u_j] ∈ T^{m×j}`
12//! with orthonormal columns (right and left Lanczos vectors); `B_j ∈ T^{j×j}`
13//! upper triangular. After `j` steps
14//!
15//! ```text
16//! A P_j = U_j B_j (B-left)
17//! Aᵀ U_j = P_j B_jᵀ + β_j p_{j+1} e_jᵀ, p_{j+1} ⟂ P_j (B-right)
18//! ```
19//!
20//! Before the first restart `B_j` is upper bidiagonal (`α_i` on the
21//! diagonal, `β_i` above it). After a restart that kept `k′` triplets it is
22//! `diag(σ̃_1 … σ̃_{k′})` with a **spike** `ρ` in column `k′ + 1`, then
23//! bidiagonal again (the "arrowhead" of Baglama & Reichel). The spike
24//! follows from (B-right) of the kept triplets: `Aᵀ ũ_i = σ̃_i p̃_i + ρ_i
25//! p_{ncv+1}`, so `U_{k′}ᵀ A p_{k′+1} = (Aᵀ U_{k′})ᵀ p_{k′+1} = ρ` and the next
26//! left step is `w = A p_{k′+1} − U_{k′} ρ`. `τ` is the tolerance of step B5
27//! (`τ = ε_T` when [`SvdsOptions::tol`] is `0`), `σ̃_1` the largest Ritz
28//! value. **Locked** triplets (`n_L` of them, always the first columns)
29//! have `ρ_i = 0`, so `B` is block diagonal: `diag(σ̃_L)` and the *active*
30//! block, which is all that Steps B4–B6 touch.
31//!
32//! ## Algorithm B (thick-restart Lanczos bidiagonalization)
33//! B1. \[Start.\] `p_1 ← v0/‖v0‖` (`v0` from the options, or `n` Gaussian
34//! deviates of the seed's stream, Algorithm G); `j ← 0`; `k′ ← 0`;
35//! `n_L ← 0`; `σ̃_est ← 0`.
36//! B2. \[Left step.\] `j ← j + 1`; `w ← A p_j − Σ_{i<j} b_{ij} u_i` (the
37//! recurrence: `β_{j−1} u_{j−1}`, or `U_{k′} ρ` right after a restart);
38//! **reorthogonalize against all of `U_{j−1}`** and take `α_j ← ‖w‖`,
39//! `u_j ← w/α_j` by Algorithm E of Chapter 12.0.7 with `floor = ε_T
40//! σ̃_est` (breakdown: `α_j ← 0`, `u_j` from the seed's stream). `b_jj ←
41//! α_j`.
42//! B3. \[Right step.\] `r ← Aᵀ u_j − α_j p_j`; **reorthogonalize against all
43//! of `P_j`**, `β_j`, `p_{j+1}` by Algorithm E as in B2. `b_{j,j+1} ←
44//! β_j` (or `β_ncv ← β_j` when `j = ncv`). `σ̃_est ← max(σ̃_est, √(α_j² +
45//! β_j²))`. If `j < ncv`, go to B2.
46//! B4. \[Ritz.\] SVD of the active block `B_act = X Σ̃ Yᵀ` by one-sided Jacobi
47//! (Algorithm J, Chapter 12.0.6), values nonincreasing. Active Ritz
48//! triplets `(σ̃_i, U_act X e_i, P_act Y e_i)`; by (B-left)/(B-right) `A
49//! p̃_i = σ̃_i ũ_i` and `Aᵀ ũ_i − σ̃_i p̃_i = ρ_i p_{ncv+1}`, `ρ_i = β_ncv ·
50//! e_lastᵀ X e_i`. `σ̃_1 ←` the largest of the locked and active values.
51//! B5. \[Test.\] The *wanted* are the `k` largest among the locked and the
52//! active Ritz values (ties: locked first). Locked ones are converged;
53//! an active one when `|ρ_i| ≤ τ σ̃_1` (**absolute**: a test relative to
54//! `σ̃_i` is unattainable for small `σ_i` and is not offered). If the `k`
55//! wanted are converged, go to B7. If the restart limit is reached,
56//! [`StatlaError::NoConvergence`] (or, with `allow_partial`, B7 with the
57//! converged ones).
58//! B6. \[Thick restart.\] Lock the converged wanted active triplets
59//! (appended to the locked block in value order; their `ρ_i` becomes
60//! `0`, a perturbation of `A` of norm `≤ τ σ̃_1`, and their vectors are
61//! never rotated again). Choose `k′` by Algorithm K of Chapter 12.0.7
62//! (`n_conv` = the converged wanted) and keep the `k′ − n_L` largest
63//! unlocked active triplets: `P ← [P_L, P_act Y_kept, p_{ncv+1}]`, `U ←
64//! [U_L, U_act X_kept]`, `B ← diag(σ̃_L, σ̃_kept)` with the spike `(0,
65//! ρ_kept)` in column `k′ + 1`. Count a restart; `j ← k′`; go to B2.
66//! B7. \[Result.\] The (converged) wanted, nonincreasing: locked ones as
67//! stored, active ones as `U_act X e_i`, `P_act Y e_i`.
68//!
69//! **Reorthogonalization policy:** full and two-sided (B2 against `U`, B3
70//! against `P`, locked vectors included); at most two Gram–Schmidt passes
71//! per step. Cost per step: two operator applications plus `≈ 4(m + n) j`
72//! flops. One-sided (Simon & Zha) and partial (PROPACK, Larsen)
73//! reorthogonalization are candidates for a measured later version.
74//!
75//! ## Invariants
76//! (G1) `‖P_jᵀP_j − I‖, ‖U_jᵀU_j − I‖ ≤ c_G · j · u` — debug-asserted at
77//! every restart (with `c_G` = `C_G`); measured in the tests.
78//! (G2) `‖A P_j − U_j B_j‖` and `‖Aᵀ U_j − P_j B_jᵀ − β_j p_{j+1} e_jᵀ‖ ≤ c_G
79//! · j · u · σ̃_est` after every expansion: computed by the unit tests
80//! (it costs `2j` extra applications, so it is not a `debug_assert!`:
81//! the operator may count its calls).
82//! (G3) `B` is upper triangular: diagonal in the kept block, the spike in
83//! column `k′ + 1`, bidiagonal after it; locked rows are zero off the
84//! diagonal — by construction, debug-asserted.
85//! (G4) `σ̃` nonincreasing (Algorithm J), nonnegative, finite — the operator
86//! output is checked for NaN/∞ after every application.
87//! (G5) A locked triplet is never modified again and its `ρ_i` is zero — by
88//! construction (Steps B4–B6 touch only the active block).
89//!
90//! ## Guarantee
91//! For every returned triplet let `r = (A v − σ̂ u; Aᵀ u − σ̂ v)`. The
92//! symmetric Jordan–Wielandt matrix `M = [0 A; Aᵀ 0]` has eigenvalues `±σ_j`
93//! and `|m − n|` zeros, and `w = (u; v)/√2` is a unit vector (to (G1)) with
94//! `M w − σ̂ w = r/√2`. By the residual bound for symmetric matrices (for
95//! unit `w`, `min_λ |λ − σ̂| ≤ ‖Mw − σ̂w‖`: expand `w` in the eigenvectors of
96//! `M`), **some** `σ_j` (or `0`) satisfies `|σ̂ − σ_j| ≤ ‖r‖/√2`. The
97//! algorithm makes `‖r‖ ≤ (τ + c_G · ncv · u) σ̃_1`: the first term is step
98//! B5 (`|ρ_i| ≤ τ σ̃_1` is the right half of `r` in exact arithmetic, and
99//! the left half is zero), the second the rounding of the relations and the
100//! loss of orthogonality, bounded by (G1)–(G2) with a *measured* constant.
101//! Two limits: the index `j` is the `i`-th only if no copy of a multiple
102//! singular value was missed (a single-vector Krylov method can miss
103//! multiplicities: in exact arithmetic it sees one copy only), and the
104//! error is absolute — small singular values carry `ε σ_1`, not `ε σ_i`.
105//!
106//! **The constant** `c_G = C_G = 8` (measured in task L3.3, margin 3.5×):
107//! the largest recomputed `(‖r‖/σ̂_1 − τ)/(ncv·u)` over the acceptance
108//! cases was `2.3` in `f64` (`2000 × 200`; `≤ 1.4` for `m ≤ 300`) and `0.05`
109//! in double-double; (G2) at most `0.85·ncv·u·σ̃_est`; (G1) at most
110//! `1.1·ncv·u` (`l33-tables.md`).
111//!
112//! ## Acceptance (L3.3, S9; as ratified, with the oracle used)
113//! (i) every returned triplet: the recomputed `‖r‖ ≤ (τ + c_G·ncv·u) σ̂_1`;
114//! (ii) `|σ̂_i − σ_i| ≤ 10⁻¹³ σ_1` (`f64`) on matrices with prescribed
115//! spectra down to `10⁻¹⁴ σ_1`, clusters included, where the gap to the
116//! neighbours is `≥ 10⁻⁸ σ_1` — the reference SVD is the construction
117//! itself, certified to `u‖A‖_F` by Weyl, and cross-checked against a
118//! one-sided Jacobi SVD in double-double (tests/svds.rs); (iii) against
119//! `scipy.sparse.linalg.svds` on Matrix Market matrices, `1e-10` relative
120//! on the `σ_i ≥ 10⁻³σ_1` with gap `≥ 10⁻⁶σ_1` — moved to task L3.4
121//! (D-0134), in CI on committed fixtures (tests/arpack.rs); (iv)
122//! `DoubleDouble`: (i) with `u = 2⁻¹⁰⁵`.
123//!
124//! ## References
125//! Golub & Kahan, "Calculating the singular values and pseudo-inverse of
126//! a matrix", SIAM J. Numer. Anal. 2 (1965); Baglama & Reichel, "Augmented
127//! implicitly restarted Lanczos bidiagonalization methods", SISC 27 (2005)
128//! (the arrowhead after a thick restart; `irlba`); Wu & Simon,
129//! "Thick-restart Lanczos method for large symmetric eigenvalue problems",
130//! SIMAX 22 (2000); Simon & Zha, SISC 21 (2000); Larsen, DAIMI PB-537
131//! (1998); Daniel, Gragg, Kaufman & Stewart (1976); Parlett, *The Symmetric
132//! Eigenvalue Problem* (1998), Thm. 4.5.1 (the residual bound). Cited from
133//! memory.
134
135use xingo_sparse::{DenseBlock, Real};
136
137use crate::StatlaError;
138use crate::error::op_err;
139use crate::jacobi::{JacobiOptions, jacobi_svd};
140use crate::krylov::{expand, kept_dimension};
141use crate::operator::AdjointOperator;
142use crate::random::Rng;
143use crate::real::{is_exact_zero, le_exact, lt};
144use crate::rsvd::{Svd, SvdStats};
145use crate::small::{axpy_sub, check_finite, check_len, dot, norm2};
146
147/// The constant `c_G` of invariants (G1)–(G2) and of the guarantee
148/// `‖r‖ ≤ (τ + c_G·ncv·u)σ̂_1` (measured in task L3.3, with a margin).
149pub(crate) const C_G: f64 = 8.0;
150
151/// Which singular values [`svds()`] computes. v0.1 has only the largest;
152/// the smallest (harmonic Ritz or refined restarts, Baglama & Reichel;
153/// cited from memory) would be a new variant, hence `#[non_exhaustive]`.
154#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
155#[non_exhaustive]
156pub enum SvdWhich {
157 /// The `k` largest (scipy's `which='LM'`, the default everywhere).
158 #[default]
159 Largest,
160}
161
162/// Options of [`svds()`]. Defaults are scipy's `svds` where it has one
163/// (cited from memory), with ARPACK's dimension rule.
164#[derive(Clone, Debug, PartialEq)]
165pub struct SvdsOptions<T: Real = f64> {
166 /// Which values (default [`SvdWhich::Largest`]).
167 pub which: SvdWhich,
168 /// Krylov dimension `ncv` (number of right Lanczos vectors kept before
169 /// a restart); `None` = `min(min(m, n), max(2k + 1, 20))`. Must satisfy
170 /// `k < ncv ≤ min(m, n)`.
171 pub ncv: Option<usize>,
172 /// `τ` of the convergence test (step B5); `0` (default) means
173 /// `T::EPSILON`. *Absolute* in units of `σ̃_1`, the largest Ritz value:
174 /// a relative test `≤ τ σ̃_i` is unattainable for small `σ_i` and is
175 /// not offered.
176 pub tol: f64,
177 /// Restart limit; `None` = `10 · min(m, n)`.
178 pub max_restarts: Option<usize>,
179 /// Starting right vector `p_1 ∈ R^n`; `None` = Gaussian from
180 /// [`SvdsOptions::seed`] (Algorithm G).
181 pub v0: Option<Vec<T>>,
182 /// Seed of the starting vector and of the replacement vectors after a
183 /// breakdown (default 0).
184 pub seed: u64,
185 /// DGKS threshold of both reorthogonalizations (default `1/√2`).
186 pub reorth_eta: f64,
187 /// Compute the singular vectors (default `true`); with `false`, `u`
188 /// and `v` of the result are `0`-column blocks.
189 pub vectors: bool,
190 /// On non-convergence return the converged triplets (`Ok`, fewer than
191 /// `k`) instead of [`StatlaError::NoConvergence`] (default `false`).
192 pub allow_partial: bool,
193}
194
195impl<T: Real> Default for SvdsOptions<T> {
196 fn default() -> Self {
197 Self {
198 which: SvdWhich::Largest,
199 ncv: None,
200 tol: 0.0,
201 max_restarts: None,
202 v0: None,
203 seed: 0,
204 reorth_eta: core::f64::consts::FRAC_1_SQRT_2,
205 vectors: true,
206 allow_partial: false,
207 }
208 }
209}
210
211/// The validated parameters of one run.
212struct Params<T> {
213 ncv: usize,
214 tau: T,
215 eta: T,
216 max_restarts: usize,
217}
218
219fn invalid(what: &'static str) -> StatlaError {
220 StatlaError::InvalidArgument { what }
221}
222
223/// Check the arguments (in the order of the error conventions, 12.0.1).
224fn validate<T: Real>(
225 m: usize,
226 n: usize,
227 k: usize,
228 o: &SvdsOptions<T>,
229) -> Result<Params<T>, StatlaError> {
230 let mn = m.min(n);
231 if k == 0 || k >= mn {
232 return Err(invalid("svds: k must satisfy 1 <= k < min(m, n)"));
233 }
234 let ncv = o.ncv.unwrap_or_else(|| mn.min((2 * k + 1).max(20)));
235 if ncv <= k || ncv > mn {
236 return Err(invalid("svds: ncv must satisfy k < ncv <= min(m, n)"));
237 }
238 if !o.tol.is_finite() || lt(o.tol, 0.0) {
239 return Err(invalid("svds: tol must be finite and >= 0"));
240 }
241 if !o.reorth_eta.is_finite() || !lt(0.0, o.reorth_eta) || !lt(o.reorth_eta, 1.0) {
242 return Err(invalid("svds: reorth_eta must lie in (0, 1)"));
243 }
244 if let Some(v0) = &o.v0 {
245 check_len("v0", n, v0.len())?;
246 check_finite("v0", v0)?;
247 if is_exact_zero(norm2(v0)) {
248 return Err(invalid("svds: v0 is the zero vector"));
249 }
250 }
251 let tau = if is_exact_zero(o.tol) {
252 T::EPSILON
253 } else {
254 T::from_f64(o.tol)
255 };
256 Ok(Params {
257 ncv,
258 tau,
259 eta: T::from_f64(o.reorth_eta),
260 max_restarts: o.max_restarts.unwrap_or(10 * mn),
261 })
262}
263
264/// Where a candidate of step B5 lives.
265#[derive(Clone, Copy, Debug)]
266enum Slot {
267 /// Locked column `i`.
268 Locked(usize),
269 /// Active Ritz triplet `i` (column of `X`, `Y`).
270 Active(usize),
271}
272
273/// One candidate of step B5.
274#[derive(Clone, Copy, Debug)]
275struct Cand<T> {
276 value: T,
277 slot: Slot,
278 converged: bool,
279}
280
281/// The state of Algorithm B.
282struct Engine<T: Real> {
283 m: usize,
284 n: usize,
285 ncv: usize,
286 /// `P`, `n × (ncv + 1)`.
287 p: Vec<T>,
288 /// `U`, `m × ncv`.
289 u: Vec<T>,
290 /// `B`, `ncv × ncv`.
291 b: DenseBlock<T>,
292 /// `β_ncv`.
293 beta_last: T,
294 /// Locked count `n_L`.
295 nl: usize,
296 /// `σ̃_est`.
297 sigma_est: T,
298 rng: Rng,
299 stats: SvdStats,
300 /// Largest (G2) residual over the expansions, in units of `σ̃_est`
301 /// (unit tests only).
302 #[cfg(test)]
303 g2: Option<f64>,
304}
305
306/// `y ← A x` (or `Aᵀ x`) with the counters and the NaN check.
307fn apply<T: Real, O: AdjointOperator<T> + ?Sized>(
308 op: &mut O,
309 x: &[T],
310 y: &mut [T],
311 transpose: bool,
312 stats: &mut SvdStats,
313) -> Result<(), StatlaError> {
314 if transpose {
315 op.apply_t(x, y).map_err(op_err)?;
316 stats.applies_t += 1;
317 } else {
318 op.apply(x, y).map_err(op_err)?;
319 stats.applies += 1;
320 }
321 check_finite("operator output", y)
322}
323
324impl<T: Real> Engine<T> {
325 /// Steps B2–B3 for `j = from, …, ncv − 1` (0-based).
326 fn expand_from<O: AdjointOperator<T> + ?Sized>(
327 &mut self,
328 op: &mut O,
329 from: usize,
330 eta: T,
331 ) -> Result<(), StatlaError> {
332 let (m, n, ncv) = (self.m, self.n, self.ncv);
333 let mut w = vec![T::ZERO; m];
334 let mut r = vec![T::ZERO; n];
335 for j in from..ncv {
336 // B2.
337 apply(
338 op,
339 &self.p[j * n..(j + 1) * n],
340 &mut w,
341 false,
342 &mut self.stats,
343 )?;
344 for i in 0..j {
345 let bij = self.b.data[i + j * ncv];
346 if !is_exact_zero(bij) {
347 axpy_sub(bij, &self.u[i * m..(i + 1) * m], &mut w);
348 }
349 }
350 let floor = T::EPSILON * self.sigma_est;
351 let alpha = expand(
352 &self.u,
353 m,
354 j,
355 &mut w,
356 eta,
357 floor,
358 &mut self.rng,
359 &mut self.stats.reorthogonalizations,
360 );
361 self.u[j * m..(j + 1) * m].copy_from_slice(&w);
362 self.b.data[j + j * ncv] = alpha;
363 // B3.
364 apply(
365 op,
366 &self.u[j * m..(j + 1) * m],
367 &mut r,
368 true,
369 &mut self.stats,
370 )?;
371 axpy_sub(alpha, &self.p[j * n..(j + 1) * n], &mut r);
372 let floor = T::EPSILON * self.sigma_est.max(alpha);
373 let beta = expand(
374 &self.p,
375 n,
376 j + 1,
377 &mut r,
378 eta,
379 floor,
380 &mut self.rng,
381 &mut self.stats.reorthogonalizations,
382 );
383 self.p[(j + 1) * n..(j + 2) * n].copy_from_slice(&r);
384 if j + 1 < ncv {
385 self.b.data[j + (j + 1) * ncv] = beta;
386 } else {
387 self.beta_last = beta;
388 }
389 self.sigma_est = self.sigma_est.max((alpha * alpha + beta * beta).sqrt());
390 }
391 Ok(())
392 }
393
394 /// (G2), unit tests only: the two relations after a full expansion.
395 #[cfg(test)]
396 fn relations<O: AdjointOperator<T> + ?Sized>(&mut self, op: &mut O) -> f64 {
397 let (m, n, ncv) = (self.m, self.n, self.ncv);
398 let mut worst = 0.0f64;
399 let mut y = vec![T::ZERO; m];
400 let mut z = vec![T::ZERO; n];
401 for j in 0..ncv {
402 op.apply(&self.p[j * n..(j + 1) * n], &mut y).unwrap();
403 for i in 0..=j {
404 axpy_sub(
405 self.b.data[i + j * ncv],
406 &self.u[i * m..(i + 1) * m],
407 &mut y,
408 );
409 }
410 worst = worst.max(norm2(&y).to_f64());
411 op.apply_t(&self.u[j * m..(j + 1) * m], &mut z).unwrap();
412 for i in j..ncv {
413 axpy_sub(
414 self.b.data[j + i * ncv],
415 &self.p[i * n..(i + 1) * n],
416 &mut z,
417 );
418 }
419 if j + 1 == ncv {
420 axpy_sub(self.beta_last, &self.p[ncv * n..(ncv + 1) * n], &mut z);
421 }
422 worst = worst.max(norm2(&z).to_f64());
423 }
424 worst / self.sigma_est.to_f64().max(f64::MIN_POSITIVE)
425 }
426
427 /// The active block `B[nl.., nl..]`.
428 fn active_block(&self) -> DenseBlock<T> {
429 let (ncv, nl) = (self.ncv, self.nl);
430 let na = ncv - nl;
431 let mut a = DenseBlock::zeros(na, na);
432 for j in 0..na {
433 for i in 0..=j {
434 a.data[i + j * na] = self.b.data[nl + i + (nl + j) * ncv];
435 }
436 }
437 a
438 }
439
440 /// The active Ritz vector `U_act X e_c` (left) or `P_act Y e_c`.
441 fn ritz(&self, coef: &DenseBlock<T>, c: usize, left: bool) -> Vec<T> {
442 let (rows, base) = if left {
443 (self.m, &self.u)
444 } else {
445 (self.n, &self.p)
446 };
447 let na = coef.rows;
448 let mut out = vec![T::ZERO; rows];
449 for t in 0..na {
450 let f = coef.data[t + c * na];
451 let col = &base[(self.nl + t) * rows..(self.nl + t + 1) * rows];
452 for (o, &v) in out.iter_mut().zip(col) {
453 *o += v * f;
454 }
455 }
456 out
457 }
458
459 /// (G3), debug builds, right after a restart to `k′ = kp`: the locked and
460 /// kept rows are zero off the diagonal except the spike column `kp`
461 /// (and the locked rows are zero there too), nothing beyond `kp`.
462 fn arrowhead_shape(&self, kp: usize) -> bool {
463 let ncv = self.ncv;
464 for j in 0..ncv {
465 for i in 0..ncv {
466 let v = self.b.data[i + j * ncv];
467 let allowed = (i == j && j < kp) || (j == kp && i >= self.nl && i < kp);
468 if !allowed && !is_exact_zero(v) {
469 return false;
470 }
471 }
472 }
473 true
474 }
475
476 /// (G1), debug builds: orthonormality of `P_{j+1}` and `U_j`.
477 fn orthogonality(&self, j: usize) -> f64 {
478 let mut e = 0.0f64;
479 for (base, rows, cols) in [(&self.p, self.n, j + 1), (&self.u, self.m, j)] {
480 for a in 0..cols {
481 for c in 0..=a {
482 let d = dot(
483 &base[a * rows..(a + 1) * rows],
484 &base[c * rows..(c + 1) * rows],
485 );
486 let t = if a == c { d - T::ONE } else { d };
487 // A zero column (the no-room case of Algorithm E) is exempt.
488 if a == c && is_exact_zero(d) {
489 continue;
490 }
491 e = e.max(t.abs().to_f64());
492 }
493 }
494 }
495 e
496 }
497}
498
499/// Leading `k` singular triplets by Golub–Kahan–Lanczos bidiagonalization
500/// with thick restart — a Krylov engine of its own, not an eigensolver on
501/// `AᵀA` (S2): it never squares the condition, so every singular value
502/// comes out with an *absolute* error of order `ε σ_1`.
503///
504/// Algorithm B of Chapter 12.5: full two-sided DGKS reorthogonalization,
505/// one-sided Jacobi SVD of the projected matrix, thick restart in the
506/// arrowhead form of Baglama & Reichel, locking of converged triplets,
507/// absolute convergence test `|ρ_i| ≤ τ σ̃_1`.
508///
509/// **Guarantee.** Every returned triplet has `‖(A v − σ̂ u; Aᵀ u − σ̂ v)‖ ≤
510/// (τ + c_G·ncv·u) σ̂_1` (`c_G = 8`, measured; Chapter 12.5), hence some singular value
511/// `σ_j` (or 0) lies within `‖r‖/√2` of `σ̂` (Jordan–Wielandt; proved in the
512/// chapter). The index `j` is the `i`-th unless a copy of a multiple value
513/// was missed.
514///
515/// # Errors
516/// [`StatlaError::InvalidArgument`] (`k = 0`; `k ≥ min(m, n)`; `ncv ∉ (k,
517/// min(m, n)]`; `tol < 0` or not finite; `reorth_eta ∉ (0, 1)`; `v0 = 0`),
518/// [`StatlaError::Dimension`] (`v0`), [`StatlaError::NonFinite`] (`v0`, or
519/// the operator returned NaN/∞), [`StatlaError::Operator`],
520/// [`StatlaError::NoConvergence`].
521pub fn svds<T, O>(op: &mut O, k: usize, opts: &SvdsOptions<T>) -> Result<Svd<T>, StatlaError>
522where
523 T: Real,
524 O: AdjointOperator<T> + ?Sized,
525{
526 run(op, k, opts, false).map(|(svd, _)| svd)
527}
528
529/// Diagnostics of a run (read by the unit tests).
530#[derive(Clone, Copy, Debug)]
531#[cfg_attr(not(test), allow(dead_code))]
532struct Diag {
533 /// Largest (G2) residual / `σ̃_est` (with `paranoid`; else 0).
534 g2: f64,
535 /// Triplets locked at the end.
536 locked: usize,
537}
538
539/// Algorithm B; with `paranoid` (unit tests) the largest (G2) residual is
540/// returned in the diagnostics.
541#[allow(clippy::too_many_lines)]
542fn run<T, O>(
543 op: &mut O,
544 k: usize,
545 opts: &SvdsOptions<T>,
546 paranoid: bool,
547) -> Result<(Svd<T>, Diag), StatlaError>
548where
549 T: Real,
550 O: AdjointOperator<T> + ?Sized,
551{
552 let (m, n) = (op.nrows(), op.ncols());
553 let par = validate(m, n, k, opts)?;
554 let ncv = par.ncv;
555 let _ = paranoid;
556 // B1.
557 let mut rng = Rng::new(opts.seed);
558 let mut p = vec![T::ZERO; n * (ncv + 1)];
559 match &opts.v0 {
560 Some(v0) => p[..n].copy_from_slice(v0),
561 None => rng.fill(crate::Sketch::Gaussian, &mut p[..n]),
562 }
563 let nv = norm2(&p[..n]);
564 for v in &mut p[..n] {
565 *v = *v / nv;
566 }
567 let mut e = Engine {
568 m,
569 n,
570 ncv,
571 p,
572 u: vec![T::ZERO; m * ncv],
573 b: DenseBlock::zeros(ncv, ncv),
574 beta_last: T::ZERO,
575 nl: 0,
576 sigma_est: T::ZERO,
577 rng,
578 stats: SvdStats::default(),
579 #[cfg(test)]
580 g2: None,
581 };
582 let mut locked: Vec<T> = Vec::new();
583 let mut from = 0;
584 let jopts = JacobiOptions::for_rows(ncv);
585 loop {
586 // B2–B3.
587 e.expand_from(op, from, par.eta)?;
588 #[cfg(test)]
589 if paranoid {
590 let g = e.relations(op);
591 e.g2 = Some(e.g2.map_or(g, |h: f64| h.max(g)));
592 }
593 // B4.
594 let na = ncv - e.nl;
595 let small = jacobi_svd(&e.active_block(), &jopts)?;
596 let rho: Vec<T> = (0..na)
597 .map(|i| e.beta_last * small.x.data[(na - 1) + i * na])
598 .collect();
599 let mut sigma1 = small.s[0];
600 for &v in &locked {
601 sigma1 = sigma1.max(v);
602 }
603 // B5.
604 let thresh = par.tau * sigma1;
605 let mut cands: Vec<Cand<T>> = Vec::with_capacity(ncv);
606 for (i, &v) in locked.iter().enumerate() {
607 cands.push(Cand {
608 value: v,
609 slot: Slot::Locked(i),
610 converged: true,
611 });
612 }
613 for i in 0..na {
614 cands.push(Cand {
615 value: small.s[i],
616 slot: Slot::Active(i),
617 converged: le_exact(rho[i].abs(), thresh),
618 });
619 }
620 // Stable sort by value, locked first on ties (they come first).
621 cands.sort_by(|a, b| {
622 if lt(b.value, a.value) {
623 core::cmp::Ordering::Less
624 } else if lt(a.value, b.value) {
625 core::cmp::Ordering::Greater
626 } else {
627 core::cmp::Ordering::Equal
628 }
629 });
630 let wanted = &cands[..k];
631 let n_conv = wanted.iter().filter(|c| c.converged).count();
632 let limit = e.stats.restarts >= par.max_restarts;
633 if n_conv == k || limit {
634 if n_conv < k && !opts.allow_partial {
635 return Err(StatlaError::NoConvergence {
636 requested: k,
637 converged: n_conv,
638 restarts: e.stats.restarts,
639 });
640 }
641 // B7.
642 let take: Vec<Cand<T>> = wanted.iter().copied().filter(|c| c.converged).collect();
643 let cols = if opts.vectors { take.len() } else { 0 };
644 let mut uo = DenseBlock::zeros(m, cols);
645 let mut vo = DenseBlock::zeros(n, cols);
646 let mut s = Vec::with_capacity(take.len());
647 for (c, cand) in take.iter().enumerate() {
648 s.push(cand.value);
649 if !opts.vectors {
650 continue;
651 }
652 let (uc, vc) = match cand.slot {
653 Slot::Locked(i) => (
654 e.u[i * m..(i + 1) * m].to_vec(),
655 e.p[i * n..(i + 1) * n].to_vec(),
656 ),
657 Slot::Active(i) => (e.ritz(&small.x, i, true), e.ritz(&small.y, i, false)),
658 };
659 uo.data[c * m..(c + 1) * m].copy_from_slice(&uc);
660 vo.data[c * n..(c + 1) * n].copy_from_slice(&vc);
661 }
662 let mut stats = e.stats;
663 stats.converged = s.len();
664 #[cfg(test)]
665 let g2 = e.g2.unwrap_or(0.0);
666 #[cfg(not(test))]
667 let g2 = 0.0;
668 let diag = Diag { g2, locked: e.nl };
669 return Ok((
670 Svd {
671 u: uo,
672 s,
673 v: vo,
674 stats,
675 },
676 diag,
677 ));
678 }
679 // B6.
680 e.stats.restarts += 1;
681 let newly: Vec<usize> = wanted
682 .iter()
683 .filter_map(|c| match c.slot {
684 Slot::Active(i) if c.converged => Some(i),
685 _ => None,
686 })
687 .collect();
688 let nl_new = e.nl + newly.len();
689 let kp = kept_dimension(k, ncv, n_conv, nl_new);
690 let kept: Vec<usize> = (0..na)
691 .filter(|i| !newly.contains(i))
692 .take(kp - nl_new)
693 .collect();
694 let (mut pn, mut un) = (e.p.clone(), e.u.clone());
695 let mut bn = DenseBlock::zeros(ncv, ncv);
696 for i in 0..e.nl {
697 bn.data[i + i * ncv] = e.b.data[i + i * ncv];
698 }
699 for (slot, &i) in newly.iter().chain(&kept).enumerate() {
700 let col = e.nl + slot;
701 un[col * m..(col + 1) * m].copy_from_slice(&e.ritz(&small.x, i, true));
702 pn[col * n..(col + 1) * n].copy_from_slice(&e.ritz(&small.y, i, false));
703 bn.data[col + col * ncv] = small.s[i];
704 if col >= nl_new {
705 bn.data[col + kp * ncv] = rho[i];
706 }
707 }
708 pn[kp * n..(kp + 1) * n].copy_from_slice(&e.p[ncv * n..(ncv + 1) * n]);
709 for &i in &newly {
710 locked.push(small.s[i]);
711 }
712 e.p = pn;
713 e.u = un;
714 e.b = bn;
715 e.nl = nl_new;
716 from = kp;
717 debug_assert!(e.arrowhead_shape(kp), "(G3) arrowhead after a restart");
718 #[allow(clippy::cast_precision_loss)]
719 let g1 = C_G * (ncv as f64) * T::EPSILON.to_f64() / 2.0;
720 debug_assert!(
721 e.orthogonality(kp) <= g1,
722 "(G1) after a restart: {}",
723 e.orthogonality(kp)
724 );
725 }
726}
727
728#[cfg(test)]
729#[allow(clippy::cast_precision_loss)]
730mod tests {
731 use super::*;
732 use xingo_extprec::DoubleDouble as Dd;
733
734 /// A diagonal `m × n` operator with prescribed values, rotated by a
735 /// fixed reflector on each side so that the start vector is generic.
736 fn test_matrix<T: Real>(m: usize, n: usize, s: &[f64], seed: u64) -> DenseBlock<T> {
737 let mut a = DenseBlock::<T>::zeros(m, n);
738 for (i, &v) in s.iter().enumerate() {
739 a.data[i + i * m] = T::from_f64(v);
740 }
741 let mut rng = Rng::new(seed);
742 for _ in 0..3 {
743 let v: Vec<T> = (0..m).map(|_| T::from_f64(rng.gaussian())).collect();
744 let vv = dot(&v, &v);
745 for j in 0..n {
746 let col = &mut a.data[j * m..(j + 1) * m];
747 let f = T::from_f64(2.0) * dot(col, &v) / vv;
748 axpy_sub(f, &v, col);
749 }
750 let w: Vec<T> = (0..n).map(|_| T::from_f64(rng.gaussian())).collect();
751 let ww = dot(&w, &w);
752 for i in 0..m {
753 let d: T = (0..n).map(|j| a.data[i + j * m] * w[j]).sum();
754 let f = T::from_f64(2.0) * d / ww;
755 for j in 0..n {
756 a.data[i + j * m] -= f * w[j];
757 }
758 }
759 }
760 a
761 }
762
763 fn g2_of<T: Real>(u: f64) -> f64 {
764 let s: Vec<f64> = (0..60).map(|j| 0.9f64.powi(j)).collect();
765 let mut a = test_matrix::<T>(90, 60, &s, 5);
766 let (f, d) = run(&mut a, 6, &SvdsOptions::default(), true).unwrap();
767 assert!(f.stats.restarts > 0, "the test must restart");
768 assert!(d.locked > 0, "the test must lock");
769 d.g2 / (20.0 * u)
770 }
771
772 /// (G2): the relations hold to `c_G·ncv·u·σ̃_est` after every expansion,
773 /// restarts included.
774 #[test]
775 fn relations_hold_after_every_expansion() {
776 let r64 = g2_of::<f64>(f64::EPSILON / 2.0);
777 let rdd = g2_of::<Dd>(Dd::EPSILON.to_f64() / 2.0);
778 eprintln!("(G2) / (ncv u): f64 {r64:.3}, dd {rdd:.3}");
779 assert!(r64 <= C_G && rdd <= C_G, "{r64} {rdd}");
780 }
781
782 /// (G5) and B6: on a slowly converging spectrum triplets are locked, and
783 /// a locked triplet's right residual is its dropped `ρ` (`≤ τ σ̃_1`).
784 #[test]
785 fn converged_triplets_are_locked() {
786 let s: Vec<f64> = (0..80).map(|j| 1.0 / (1.0 + 0.05 * f64::from(j))).collect();
787 let mut a = test_matrix::<f64>(100, 80, &s, 2);
788 let (f, d) = run(&mut a, 8, &SvdsOptions::default(), false).unwrap();
789 assert!(d.locked > 0 && f.stats.restarts > 2, "{d:?} {:?}", f.stats);
790 let mut y = vec![0.0; 80];
791 for c in 0..f.s.len() {
792 a.apply_t(&f.u.data[c * 100..(c + 1) * 100], &mut y)
793 .unwrap();
794 axpy_sub(f.s[c], &f.v.data[c * 80..(c + 1) * 80], &mut y);
795 assert!(norm2(&y) <= 1e-14 * f.s[0], "{c}: {}", norm2(&y));
796 assert!(
797 (f.s[c] - s[c]).abs() <= 1e-14,
798 "{c}: {} vs {}",
799 f.s[c],
800 s[c]
801 );
802 }
803 }
804
805 #[test]
806 fn options_are_validated() {
807 let mut a = test_matrix::<f64>(8, 6, &[3.0, 2.0, 1.0, 0.5, 0.25, 0.1], 1);
808 let d = SvdsOptions::<f64>::default();
809 let bad =
810 |o: &SvdsOptions<f64>, k: usize, a: &mut DenseBlock<f64>| svds(a, k, o).unwrap_err();
811 assert!(matches!(
812 bad(&d, 0, &mut a),
813 StatlaError::InvalidArgument { .. }
814 ));
815 assert!(matches!(
816 bad(&d, 6, &mut a),
817 StatlaError::InvalidArgument { .. }
818 ));
819 for o in [
820 SvdsOptions {
821 ncv: Some(2),
822 ..d.clone()
823 },
824 SvdsOptions {
825 ncv: Some(7),
826 ..d.clone()
827 },
828 SvdsOptions {
829 tol: -1.0,
830 ..d.clone()
831 },
832 SvdsOptions {
833 tol: f64::NAN,
834 ..d.clone()
835 },
836 SvdsOptions {
837 reorth_eta: 1.0,
838 ..d.clone()
839 },
840 SvdsOptions {
841 reorth_eta: 0.0,
842 ..d.clone()
843 },
844 SvdsOptions {
845 v0: Some(vec![0.0; 6]),
846 ..d.clone()
847 },
848 ] {
849 assert!(
850 matches!(bad(&o, 2, &mut a), StatlaError::InvalidArgument { .. }),
851 "{o:?}"
852 );
853 }
854 let o = SvdsOptions {
855 v0: Some(vec![1.0; 5]),
856 ..d.clone()
857 };
858 assert!(matches!(
859 bad(&o, 2, &mut a),
860 StatlaError::Dimension { what: "v0", .. }
861 ));
862 let o = SvdsOptions {
863 v0: Some(vec![1.0, f64::INFINITY, 0.0, 0.0, 0.0, 0.0]),
864 ..d.clone()
865 };
866 assert!(matches!(
867 bad(&o, 2, &mut a),
868 StatlaError::NonFinite {
869 what: "v0",
870 index: 1
871 }
872 ));
873 // ncv = min(m, n): the full space, converged in one pass.
874 let f = svds(
875 &mut a,
876 3,
877 &SvdsOptions {
878 ncv: Some(6),
879 ..d.clone()
880 },
881 )
882 .unwrap();
883 assert_eq!(f.stats.restarts, 0);
884 assert!((f.s[0] - 3.0).abs() < 1e-14 && (f.s[2] - 1.0).abs() < 1e-14);
885 }
886}