Skip to main content

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}