Skip to main content

xingo_statla/
jacobi.rs

1//! # Chapter 12.0.6 — One-sided Jacobi SVD of a small dense matrix
2//!
3//! ## Purpose
4//! Both truncated SVDs end with the SVD of a *small* matrix: the `l × l`
5//! triangle of step S5 of [`crate::rsvd()`] and the projected `B` of step B4
6//! of [`crate::svds()`] (and `eigsh`/`eigs` of L3.4 will reuse the sorting
7//! and completion conventions). `DenseKernel` has no SVD and the crate is
8//! generic in `T: Real` (decision S1), so this is the classical one-sided
9//! (Hestenes) Jacobi method: it needs only `+ − · /`, `sqrt` and the order,
10//! and it is backward stable column by column (Demmel & Veselić), which is
11//! what the residual guarantees of 12.4 and 12.5 rest on.
12//!
13//! ## Notation
14//! `B ∈ T^{p×q}`, `p ≥ q`; `w_i` the columns of the working copy `W`; `Y ∈
15//! T^{q×q}` the accumulated rotations, so `W = B Y` throughout; at the end
16//! `w_i = σ_i x_i` with `‖x_i‖ = 1`, hence `B Y = X Σ`, `B = X Σ Yᵀ`. `tol`
17//! and `max_sweeps` are the fields of [`JacobiOptions`].
18//!
19//! ## Algorithm J
20//! J1. \[Scale.\] `μ ← max |b_ij|`. If `μ = 0`: `Σ = 0`, `Y = I`, `X` the
21//!     first `q` columns of `I_p`; done. Otherwise `W ← B/2^⌊log₂ μ⌋`
22//!     (exact), so the squares below neither overflow nor underflow.
23//! J2. \[Sweep.\] First set to zero every column whose `‖w_i‖²` underflows
24//!     to 0 (its norm is below `2⁻⁵³⁷` while `max |w_ij| ≥ 1`: far below
25//!     `ε_T‖B‖`, so a negligible backward perturbation; without it such a
26//!     column, with `a = 0` but `γ ≠ 0`, would be rotated forever). Then for
27//!     every pair `i < j` in row-cyclic order: `a ← ‖w_i‖²`,
28//!     `b ← ‖w_j‖²`, `γ ← w_iᵀw_j`. If `|γ| > tol·√(a b)`: `ζ ← (b −
29//!     a)/(2γ)`, `t ← sign(ζ)/(|ζ| + √(1 + ζ²))` (written as `sign(ζ)/(|ζ|(1 +
30//!     √(1 + ζ⁻²)))` when `|ζ| ≥ 1`, so that `ζ²` never overflows), `c ←
31//!     1/√(1 + t²)`, `s ← c t`; `(w_i, w_j) ← (c w_i − s w_j, s w_i + c w_j)`,
32//!     the same on the columns of `Y`. This makes the new pair exactly
33//!     orthogonal in exact arithmetic (`cs(a − b) + (c² − s²)γ = 0`).
34//! J3. \[Stop.\] Stop after a sweep without rotation. After `max_sweeps`
35//!     sweeps, report non-convergence (never seen: the method converges
36//!     quadratically once the off-diagonal mass is small).
37//! J4. \[Values.\] Divide `y_i` *and* `w_i` by `‖y_i‖` (this keeps `W = B Y`
38//!     and removes the drift of the column norms of `Y`: `c² + s²` rounds
39//!     with a bias, and a column touched by `r` rotations drifts by up to
40//!     `r·u` — measured `1.3·10⁻¹⁴` for `q = 21` before this step, `8·10⁻¹⁶`
41//!     after, in task L3.3; without it the restarts of 12.5, `P ← P Y`,
42//!     compound the drift). Then `σ_i ← ‖w_i‖` (unscaled); sort
43//!     nonincreasingly (stable: ties keep their column order), permuting `W`
44//!     and `Y` alike.
45//! J5. \[Left vectors.\] `x_i ← w_i/‖w_i‖` for `σ_i > 0`. For `σ_i = 0` (an
46//!     exactly zero column) complete `X` to orthonormal columns: try `e_0,
47//!     e_1, …` in turn, orthogonalize against the columns already in `X`
48//!     (two Gram–Schmidt passes) and take the first whose remaining norm
49//!     exceeds `½`.
50//!
51//! ## Invariants
52//! (J1) `σ` nonincreasing, nonnegative, finite for finite `B`.
53//! (J2) `Y` orthogonal and `X` orthonormal to `O(tol)` — by the stopping
54//!      test, `|x_iᵀx_j| ≤ tol` *relative*, whatever the sizes of `σ_i`,
55//!      `σ_j` (this is why the one-sided method gives small singular values
56//!      with orthogonal vectors).
57//! (J3) `‖B Y − X Σ‖ ≤ c·q·u·‖B‖` (backward stability of the rotations).
58//! All three are checked by the tests below (and debug-asserted for J1).
59//!
60//! ## References
61//! Hestenes, "Inversion of matrices by biorthogonalization", J. SIAM 6
62//! (1958); Demmel & Veselić, "Jacobi's method is more accurate than QR",
63//! SIMAX 13 (1992); Golub & Van Loan, *Matrix Computations*, 4th ed.,
64//! §8.6.3; Drmač & Veselić, "New fast and accurate Jacobi SVD algorithm",
65//! SIMAX 29 (2008) (the `√p·ε` tolerance of LAPACK `dgesvj`). Cited from
66//! memory.
67
68use xingo_sparse::{DenseBlock, Real};
69
70use crate::StatlaError;
71use crate::real::{is_exact_zero, le_exact, lt};
72use crate::small::{axpy_sub, dot, norm2};
73
74/// The thresholds of Algorithm J.
75#[derive(Clone, Copy, Debug)]
76pub(crate) struct JacobiOptions<T> {
77    /// Rotate when `|w_iᵀw_j| > tol·‖w_i‖‖w_j‖`.
78    pub(crate) tol: T,
79    /// Sweep limit of J3.
80    pub(crate) max_sweeps: usize,
81}
82
83impl<T: Real> JacobiOptions<T> {
84    /// The defaults for `p` rows: `tol = √p·ε_T` (as LAPACK `dgesvj`) and
85    /// 60 sweeps (more than ten times what quadratic convergence needs at
86    /// the sizes of this crate).
87    pub(crate) fn for_rows(p: usize) -> Self {
88        #[allow(clippy::cast_precision_loss)]
89        let pf = T::from_f64(p.max(1) as f64);
90        Self {
91            tol: T::EPSILON * pf.sqrt(),
92            max_sweeps: 60,
93        }
94    }
95}
96
97/// The result `B = X diag(s) Yᵀ` of Algorithm J.
98#[derive(Clone, Debug)]
99pub(crate) struct SmallSvd<T: Real> {
100    /// Left singular vectors, `p × q`.
101    pub(crate) x: DenseBlock<T>,
102    /// Singular values, nonincreasing.
103    pub(crate) s: Vec<T>,
104    /// Right singular vectors, `q × q`.
105    pub(crate) y: DenseBlock<T>,
106    /// Sweeps performed (read by the tests and the measurements).
107    #[cfg_attr(not(test), allow(dead_code))]
108    pub(crate) sweeps: usize,
109}
110
111/// `2^⌊log₂ μ⌋` for a positive normal `μ`, `1` otherwise.
112fn pow2_floor(mu: f64) -> f64 {
113    let bits = mu.to_bits() & 0x7ff0_0000_0000_0000;
114    if bits == 0 || bits == 0x7ff0_0000_0000_0000 {
115        1.0
116    } else {
117        f64::from_bits(bits)
118    }
119}
120
121/// Rotate columns `i < j` of the `rows`-row array: `(a, b) ← (c a − s b, s
122/// a + c b)`.
123fn rotate<T: Real>(data: &mut [T], rows: usize, i: usize, j: usize, c: T, s: T) {
124    let (left, right) = data.split_at_mut(j * rows);
125    let a = &mut left[i * rows..(i + 1) * rows];
126    let b = &mut right[..rows];
127    for (x, y) in a.iter_mut().zip(b.iter_mut()) {
128        let (xa, yb) = (*x, *y);
129        *x = c * xa - s * yb;
130        *y = s * xa + c * yb;
131    }
132}
133
134/// Algorithm J on `b` (`p × q`, `p ≥ q`, finite).
135#[allow(clippy::too_many_lines)] // steps J1–J5 in one place, as in the chapter
136pub(crate) fn jacobi_svd<T: Real>(
137    b: &DenseBlock<T>,
138    opts: &JacobiOptions<T>,
139) -> Result<SmallSvd<T>, StatlaError> {
140    let (p, q) = (b.rows, b.cols);
141    debug_assert!(p >= q, "Algorithm J needs p >= q");
142    let mut y = DenseBlock::zeros(q, q);
143    for i in 0..q {
144        y.data[i + i * q] = T::ONE;
145    }
146    // J1.
147    let mut mu = T::ZERO;
148    for &v in &b.data {
149        mu = mu.max(v.abs());
150    }
151    if is_exact_zero(mu) {
152        let mut x = DenseBlock::zeros(p, q);
153        for i in 0..q {
154            x.data[i + i * p] = T::ONE;
155        }
156        return Ok(SmallSvd {
157            x,
158            s: vec![T::ZERO; q],
159            y,
160            sweeps: 0,
161        });
162    }
163    let scale = pow2_floor(mu.to_f64());
164    let inv = T::from_f64(1.0 / scale);
165    let mut w = DenseBlock {
166        rows: p,
167        cols: q,
168        data: b.data.iter().map(|&v| v * inv).collect(),
169    };
170    // J2–J3.
171    let one = T::ONE;
172    let two = T::from_f64(2.0);
173    let mut sweeps = 0;
174    loop {
175        if sweeps == opts.max_sweeps {
176            return Err(StatlaError::NoConvergence {
177                requested: q,
178                converged: 0,
179                restarts: sweeps,
180            });
181        }
182        sweeps += 1;
183        let mut rotated = false;
184        // A column whose squared norm underflows (below 2⁻¹⁰⁷⁴ after the
185        // scaling of J1, i.e. far below ε_T‖B‖) is set to exact zero: a
186        // negligible perturbation, and J5 completes it.
187        for i in 0..q {
188            let wi = &mut w.data[i * p..(i + 1) * p];
189            if is_exact_zero(dot(wi, wi)) {
190                wi.fill(T::ZERO);
191            }
192        }
193        for i in 0..q {
194            for j in i + 1..q {
195                let wi = &w.data[i * p..(i + 1) * p];
196                let wj = &w.data[j * p..(j + 1) * p];
197                let a = dot(wi, wi);
198                let bb = dot(wj, wj);
199                let g = dot(wi, wj);
200                if !lt(opts.tol * a.sqrt() * bb.sqrt(), g.abs()) {
201                    continue;
202                }
203                rotated = true;
204                let zeta = (bb - a) / (two * g);
205                let az = zeta.abs();
206                let mag = if le_exact(one, az) {
207                    let r = one / zeta;
208                    az * (one + (one + r * r).sqrt())
209                } else {
210                    az + (one + zeta * zeta).sqrt()
211                };
212                let t = if lt(zeta, T::ZERO) {
213                    -(one / mag)
214                } else {
215                    one / mag
216                };
217                let c = one / (one + t * t).sqrt();
218                let s = c * t;
219                rotate(&mut w.data, p, i, j, c, s);
220                rotate(&mut y.data, q, i, j, c, s);
221            }
222        }
223        if !rotated {
224            break;
225        }
226    }
227    // J4. Rotations computed in floating point drift the column norms of
228    // `Y` away from 1 (c² + s² rounds, with a bias); dividing `y_i` and `w_i`
229    // by the same `‖y_i‖` keeps `W = B Y` and removes the drift.
230    for i in 0..q {
231        let ny = norm2(&y.data[i * q..(i + 1) * q]);
232        for v in &mut y.data[i * q..(i + 1) * q] {
233            *v = *v / ny;
234        }
235        for v in &mut w.data[i * p..(i + 1) * p] {
236            *v = *v / ny;
237        }
238    }
239    let sc = T::from_f64(scale);
240    let norms: Vec<T> = (0..q).map(|i| norm2(&w.data[i * p..(i + 1) * p])).collect();
241    let mut order: Vec<usize> = (0..q).collect();
242    order.sort_by(|&i, &j| {
243        if lt(norms[j], norms[i]) {
244            core::cmp::Ordering::Less
245        } else if lt(norms[i], norms[j]) {
246            core::cmp::Ordering::Greater
247        } else {
248            i.cmp(&j)
249        }
250    });
251    let mut x = DenseBlock::zeros(p, q);
252    let mut ys = DenseBlock::zeros(q, q);
253    let mut s = Vec::with_capacity(q);
254    for (c, &i) in order.iter().enumerate() {
255        s.push(norms[i] * sc);
256        ys.data[c * q..(c + 1) * q].copy_from_slice(&y.data[i * q..(i + 1) * q]);
257        // J5, nonzero columns.
258        if !is_exact_zero(norms[i]) {
259            let nr = norms[i];
260            for (xv, &wv) in x.data[c * p..(c + 1) * p]
261                .iter_mut()
262                .zip(&w.data[i * p..(i + 1) * p])
263            {
264                *xv = wv / nr;
265            }
266        }
267    }
268    // J5, completion of the zero columns.
269    let half = T::from_f64(0.5);
270    let mut next_unit = 0;
271    for c in 0..q {
272        if !is_exact_zero(s[c]) {
273            continue;
274        }
275        loop {
276            debug_assert!(next_unit < p, "(J5) a completion always exists");
277            if next_unit >= p {
278                break;
279            }
280            let mut e = vec![T::ZERO; p];
281            e[next_unit] = T::ONE;
282            next_unit += 1;
283            for _ in 0..2 {
284                for k in 0..q {
285                    if k == c || (is_exact_zero(s[k]) && k > c) {
286                        continue;
287                    }
288                    let xk = &x.data[k * p..(k + 1) * p];
289                    let h = dot(xk, &e);
290                    axpy_sub(h, xk, &mut e);
291                }
292            }
293            let nu = norm2(&e);
294            if lt(half, nu) {
295                for (xv, ev) in x.data[c * p..(c + 1) * p].iter_mut().zip(&e) {
296                    *xv = *ev / nu;
297                }
298                break;
299            }
300        }
301    }
302    debug_assert!(
303        s.windows(2).all(|v| le_exact(v[1], v[0])) && s.iter().all(|v| le_exact(T::ZERO, *v)),
304        "(J1) singular values nonincreasing and nonnegative"
305    );
306    Ok(SmallSvd {
307        x,
308        s,
309        y: ys,
310        sweeps,
311    })
312}
313
314#[cfg(test)]
315#[allow(
316    clippy::cast_precision_loss,
317    clippy::cast_possible_truncation,
318    clippy::cast_possible_wrap
319)]
320mod tests {
321    use super::*;
322    use crate::random::Rng;
323    use xingo_extprec::DoubleDouble as Dd;
324
325    fn residuals<T: Real>(b: &DenseBlock<T>, f: &SmallSvd<T>) -> (f64, f64, f64) {
326        let (p, q) = (b.rows, b.cols);
327        let mut back = 0.0f64;
328        let mut ox = 0.0f64;
329        let mut oy = 0.0f64;
330        for j in 0..q {
331            for i in 0..p {
332                let mut by = T::ZERO;
333                for k in 0..q {
334                    by += b.get(i, k) * f.y.get(k, j);
335                }
336                back = back.max((by - f.x.get(i, j) * f.s[j]).abs().to_f64());
337            }
338            for i in 0..q {
339                let e = if i == j { T::ONE } else { T::ZERO };
340                let xx: T = (0..p).map(|r| f.x.get(r, i) * f.x.get(r, j)).sum();
341                let yy: T = (0..q).map(|r| f.y.get(r, i) * f.y.get(r, j)).sum();
342                ox = ox.max((xx - e).abs().to_f64());
343                oy = oy.max((yy - e).abs().to_f64());
344            }
345        }
346        (back, ox, oy)
347    }
348
349    fn graded<T: Real>(p: usize, q: usize, seed: u64) -> DenseBlock<T> {
350        // Columns scaled by 10^{-j}: singular values spread over 10^q.
351        let mut r = Rng::new(seed);
352        let mut b = DenseBlock::zeros(p, q);
353        for j in 0..q {
354            for i in 0..p {
355                b.data[i + j * p] = T::from_f64(r.gaussian() * 10f64.powi(-(j as i32)));
356            }
357        }
358        b
359    }
360
361    fn check<T: Real>(u: f64) {
362        for (p, q) in [(1, 1), (5, 3), (12, 12), (30, 17)] {
363            let b = graded::<T>(p, q, (p * 100 + q) as u64);
364            let f = jacobi_svd(&b, &JacobiOptions::for_rows(p)).unwrap();
365            let (back, ox, oy) = residuals(&b, &f);
366            let nb = f.s[0].to_f64();
367            assert!(back <= 8.0 * q as f64 * u * nb, "{p}x{q}: backward {back}");
368            assert!(ox <= 8.0 * (p as f64).sqrt() * u * 2.0, "{p}x{q}: X {ox}");
369            assert!(oy <= 8.0 * q as f64 * u, "{p}x{q}: Y {oy}");
370            assert!(f.s.windows(2).all(|v| v[1] <= v[0]));
371        }
372    }
373
374    #[test]
375    fn jacobi_is_backward_stable_with_orthogonal_factors() {
376        check::<f64>(f64::EPSILON / 2.0);
377        check::<Dd>(Dd::EPSILON.to_f64() / 2.0);
378    }
379
380    /// (J2) for `Y`: the accumulated rotations stay orthogonal to a small
381    /// multiple of `√q·u` (step J4 removes the norm drift, which otherwise
382    /// grows like the number of rotations per column).
383    #[test]
384    fn accumulated_rotations_stay_orthogonal() {
385        let mut worst = 0.0f64;
386        for seed in 0..4 {
387            let b = graded::<f64>(60, 48, 40 + seed);
388            let f = jacobi_svd(&b, &JacobiOptions::for_rows(60)).unwrap();
389            let (_, _, oy) = residuals(&b, &f);
390            worst = worst.max(oy / ((48f64).sqrt() * f64::EPSILON / 2.0));
391        }
392        eprintln!("(J2) Y: max ‖YᵀY − I‖ = {worst:.2} √q u");
393        assert!(worst <= 1.5, "{worst}");
394    }
395
396    #[test]
397    fn zero_and_rank_deficient_columns_are_completed() {
398        // Columns 1 and 3 zero, column 2 = 2·column 0.
399        let mut b = DenseBlock::<f64>::zeros(5, 4);
400        for i in 0..5 {
401            b.set(i, 0, (i + 1) as f64);
402            b.set(i, 2, 2.0 * (i + 1) as f64);
403        }
404        let f = jacobi_svd(&b, &JacobiOptions::for_rows(5)).unwrap();
405        let (back, ox, oy) = residuals(&b, &f);
406        assert!(back < 1e-14 && ox < 1e-14 && oy < 1e-14, "{back} {ox} {oy}");
407        assert!(f.s[1] < 1e-14 && f.s[2] == 0.0 && f.s[3] == 0.0);
408        let z = jacobi_svd(&DenseBlock::<f64>::zeros(3, 2), &JacobiOptions::for_rows(3)).unwrap();
409        assert_eq!(
410            (z.s.clone(), z.x.get(1, 1), z.sweeps),
411            (vec![0.0, 0.0], 1.0, 0)
412        );
413        // A diagonal input is not rotated and keeps exact values.
414        let mut d = DenseBlock::<f64>::zeros(3, 3);
415        d.set(0, 0, 2.0);
416        d.set(1, 1, 3.0);
417        d.set(2, 2, 1.0);
418        let f = jacobi_svd(&d, &JacobiOptions::for_rows(3)).unwrap();
419        assert_eq!(f.s, vec![3.0, 2.0, 1.0]);
420        assert_eq!((f.sweeps, f.y.get(1, 0), f.x.get(1, 0)), (1, 1.0, 1.0));
421    }
422
423    #[test]
424    fn extreme_scales_neither_overflow_nor_underflow() {
425        for k in [1e300, 1e-300] {
426            let mut b = graded::<f64>(6, 4, 3);
427            for v in &mut b.data {
428                *v *= k;
429            }
430            let f = jacobi_svd(&b, &JacobiOptions::for_rows(6)).unwrap();
431            let (back, ox, _) = residuals(&b, &f);
432            assert!(f.s.iter().all(|v| v.is_finite()));
433            assert!(back <= 1e-14 * f.s[0] && ox < 1e-14, "{k}: {back} {ox}");
434        }
435    }
436}