1use 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#[derive(Clone, Copy, Debug)]
76pub(crate) struct JacobiOptions<T> {
77 pub(crate) tol: T,
79 pub(crate) max_sweeps: usize,
81}
82
83impl<T: Real> JacobiOptions<T> {
84 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#[derive(Clone, Debug)]
99pub(crate) struct SmallSvd<T: Real> {
100 pub(crate) x: DenseBlock<T>,
102 pub(crate) s: Vec<T>,
104 pub(crate) y: DenseBlock<T>,
106 #[cfg_attr(not(test), allow(dead_code))]
108 pub(crate) sweeps: usize,
109}
110
111fn 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
121fn 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#[allow(clippy::too_many_lines)] pub(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 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 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 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 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 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 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 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 #[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 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 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}