use super::rotation::TransposedFactors;
use super::sweep::qr_iterate;
use super::RealScalar;
use eunomia::RealField;
fn error_bounds<T: RealScalar + RealField>(k: usize, norm: f64) -> (f64, f64) {
let order = u32::try_from(k).expect("invariant: test orders fit in u32");
let relative = 8.0 * f64::from(order) * <T as RealField>::EPSILON.to_f64();
(relative * norm, relative)
}
pub(super) fn check_bidiagonal<T: RealScalar + RealField>(
diag: &[f64],
superdiag: &[f64],
expected: &[f64],
) {
let k = diag.len();
let mut d: Vec<T> = diag.iter().map(|&x| T::from_f64(x)).collect();
let mut e: Vec<T> = (0..k)
.map(|i| T::from_f64(superdiag.get(i).copied().unwrap_or(0.0)))
.collect();
let mut ut = vec![T::ZERO; k * k];
let mut vt = vec![T::ZERO; k * k];
for i in 0..k {
ut[i * k + i] = T::ONE;
vt[i * k + i] = T::ONE;
}
qr_iterate::<T, true>(
&mut d,
&mut e,
k,
&mut TransposedFactors::new(&mut ut, k, &mut vt, k),
)
.expect("the bidiagonal iteration converges on a zero diagonal");
let (absolute, relative) = error_bounds::<T>(k, expected[0]);
let mut sigma: Vec<f64> = d.iter().map(|x| x.abs().to_f64()).collect();
sigma.sort_by(|a, b| b.total_cmp(a));
for (got, want) in sigma.iter().zip(expected) {
assert!(
(got - want).abs() <= absolute,
"σ {got} vs {want} exceeds {absolute:e}"
);
}
for row in 0..k {
for col in 0..k {
let value: f64 = (0..k)
.map(|i| ut[i * k + row].to_f64() * d[i].to_f64() * vt[i * k + col].to_f64())
.sum();
let target = if col == row {
diag[row]
} else if col == row + 1 {
superdiag[row]
} else {
0.0
};
assert!(
(value - target).abs() <= absolute,
"B[{row}][{col}] reconstructs as {value} not {target}"
);
}
}
for (name, factor) in [("U", &ut), ("V", &vt)] {
for a in 0..k {
for b in 0..k {
let dot: f64 = (0..k)
.map(|r| factor[a * k + r].to_f64() * factor[b * k + r].to_f64())
.sum();
let target = f64::from(u8::from(a == b));
assert!(
(dot - target).abs() <= relative,
"{name}ᵀ{name}[{a}][{b}] = {dot} not {target}"
);
}
}
}
}
#[test]
fn trailing_zero_diagonal_deflates_to_the_row_norm() {
check_bidiagonal::<f32>(&[3.0, 0.0], &[4.0], &[5.0, 0.0]);
check_bidiagonal::<f64>(&[3.0, 0.0], &[4.0], &[5.0, 0.0]);
}
#[test]
fn interior_zero_diagonal_chases_out_of_the_block() {
let (trace, det) = (86.0f64, 1444.0f64);
let discriminant = trace.mul_add(trace, -4.0 * det).sqrt();
let expected = [
((trace + discriminant) / 2.0).sqrt(),
((trace - discriminant) / 2.0).sqrt(),
0.0,
];
check_bidiagonal::<f32>(&[0.0, 3.0, 4.0], &[5.0, 6.0], &expected);
check_bidiagonal::<f64>(&[0.0, 3.0, 4.0], &[5.0, 6.0], &expected);
}
#[test]
fn chased_zero_singular_value_is_bit_exact() {
for (diag, superdiag) in [
(vec![3.0f64, 0.0], vec![4.0]), (vec![0.0f64, 3.0, 4.0], vec![5.0, 6.0]), ] {
let k = diag.len();
let mut d: Vec<f32> = diag.iter().map(|&x| x as f32).collect();
let mut e: Vec<f32> = (0..k)
.map(|i| superdiag.get(i).copied().unwrap_or(0.0) as f32)
.collect();
qr_iterate::<f32, false>(&mut d, &mut e, k, &mut TransposedFactors::none()).unwrap();
assert!(
d.contains(&0.0),
"the chased direction must be exactly zero, got {d:?}"
);
}
}
#[test]
fn forward_test_splits_at_tolmul_eps() {
let mut d = vec![1.0f64, 1.0, 1.0];
let mut e = vec![50.0 * f64::EPSILON, 0.5, 0.0];
let identity = |n: usize| -> Vec<f64> {
(0..n * n)
.map(|i| if i % (n + 1) == 0 { 1.0 } else { 0.0 })
.collect()
};
let (mut u, mut v) = (identity(3), identity(3));
qr_iterate::<f64, true>(
&mut d,
&mut e,
3,
&mut TransposedFactors::new(&mut u, 3, &mut v, 3),
)
.unwrap();
assert_eq!(&u[..3], &[1.0, 0.0, 0.0], "U row 0: {u:?}");
assert_eq!(&v[..3], &[1.0, 0.0, 0.0], "V row 0: {v:?}");
}
#[test]
fn gate_keeps_the_deflation_floor_below_epsilon_times_the_norm() {
use super::svd_bound;
use crate::application::linalg::scaling;
use eunomia::{FloatElement, NumericElement, F16};
let k = 64;
let mut values = vec![F16::from_f64(0.0); k * k];
values[0] = F16::from_f64(0.3);
values[1] = F16::from_f64(0.225);
let frobenius = |scale: i32| {
values
.iter()
.map(|v| v.scale_binary(scale).to_f64().powi(2))
.sum::<f64>()
.sqrt()
};
let (safmin, eps) = (2.0_f64.powi(-14), 2.0_f64.powi(-10));
let joint_floor = (k as f64).sqrt() * safmin;
assert!(joint_floor > eps * frobenius(0), "the input must violate");
let exponent = scaling::gate_exponent(&values, 2, svd_bound(k, k))
.expect("the range is non-empty")
.expect("0.3 is below the floor end");
assert!(joint_floor <= eps * frobenius(-exponent), "{exponent}");
let ones = vec![F16::from_f64(0.3); k * k];
let unmoved = scaling::gate_exponent(&ones, 2, svd_bound(k, k)).expect("non-empty");
assert_eq!(unmoved, None);
}
#[test]
fn negligible_shift_takes_the_zero_shift_sweep() {
use super::chase::Down;
use super::sweep::{qr_step, SweepWindows};
use super::zero_shift::zero_shift_sweep;
let windows = SweepWindows::<f64>::new();
let (mut d, mut e) = (vec![1.0, 1.0, 1e-9], vec![0.5, 1e-9, 0.0]);
let (mut d0, mut e0) = (d.clone(), e.clone());
qr_step::<f64, false, Down>(
&mut d,
&mut e,
0,
2,
&mut TransposedFactors::none(),
windows,
);
zero_shift_sweep::<f64, false, Down>(
&mut d0,
&mut e0,
0,
2,
&mut TransposedFactors::none(),
windows.rotation,
);
assert_eq!((d, e), (d0, e0));
}
fn zero_shift_test_scales_with_the_order_for<C: super::chase::Chase>() {
use super::chase::Oriented;
use super::deflation::Deflation;
for (x, fires) in [(1.0 / 150.0, false), (1.0 / 400.0, true)] {
let (d, e) = (vec![1.0f64, 1.0, x], vec![0.0, 0.0, 0.0]);
let (mut d, mut e) = (d, e);
let deflation = Deflation::new(&d, &e, 3);
let block = Oriented::<f64, C>::new(&mut d, &mut e, 0, 2);
assert_eq!(deflation.shift_ruins_accuracy(&block), fires, "x = {x}");
}
}
#[test]
fn zero_shift_test_scales_with_the_order_in_both_directions() {
use super::chase::{Down, Up};
zero_shift_test_scales_with_the_order_for::<Down>();
zero_shift_test_scales_with_the_order_for::<Up>();
}
fn split_reads_oriented_bounds<C: super::chase::Chase>() -> usize {
use super::chase::Oriented;
use super::deflation::Deflation;
let mut d = vec![1.0f64; 5];
let mut e = vec![1.0f64; 4];
let deflation = Deflation::new(&d, &e, 5);
let mut block = Oriented::<f64, C>::new(&mut d, &mut e, 1, 3);
block.set_e(2, 0.0);
let stored = block.stored_superdiagonal(2);
assert_eq!(deflation.split(&block), Some(stored));
stored
}
#[test]
fn split_reads_oriented_bounds_in_both_directions() {
use super::chase::{Down, Up};
assert_eq!(split_reads_oriented_bounds::<Down>(), 2);
assert_eq!(split_reads_oriented_bounds::<Up>(), 1);
}
fn largest_entry_reads_every_boundary_of_the_active_block<T: RealScalar>() {
use super::chase::{Down, Oriented};
let (five, one, half) = (T::from_count(5), T::ONE, T::ONE.div(T::from_count(2)));
let (d0, e0, e3, d4) = (
T::from_count(101),
T::from_count(103),
T::from_count(107),
T::from_count(109),
);
let mut d = vec![d0, five, one, half, d4];
let mut e = vec![
e0,
T::from_count(2).div(T::from_count(10)),
T::from_count(3).div(T::from_count(10)),
e3,
];
let block = Oriented::<T, Down>::new(&mut d, &mut e, 1, 3);
assert_eq!(block.largest_entry(), five, "d(p) must be read");
let mut d = vec![d0, half, one, five, d4];
let mut e = vec![
e0,
T::from_count(2).div(T::from_count(10)),
T::from_count(3).div(T::from_count(10)),
e3,
];
let block = Oriented::<T, Down>::new(&mut d, &mut e, 1, 3);
assert_eq!(block.largest_entry(), five, "d(q) must be read");
let seven_tenths = T::from_count(7).div(T::from_count(10));
let mut d = vec![d0, half, one, seven_tenths, d4];
let mut e = vec![e0, T::from_count(2).div(T::from_count(10)), five, e3];
let block = Oriented::<T, Down>::new(&mut d, &mut e, 1, 3);
assert_eq!(block.largest_entry(), five, "e(q-1) must be read");
}
#[test]
fn largest_entry_reads_every_boundary_of_the_active_block_across_scalar_types() {
use eunomia::{Bf16, F16};
largest_entry_reads_every_boundary_of_the_active_block::<f32>();
largest_entry_reads_every_boundary_of_the_active_block::<f64>();
largest_entry_reads_every_boundary_of_the_active_block::<F16>();
largest_entry_reads_every_boundary_of_the_active_block::<Bf16>();
}
fn zero_shift_test_scopes_smax_to_the_active_block<T: RealScalar>() {
use super::chase::{Down, Oriented};
use super::deflation::Deflation;
use crate::application::linalg::thresholds;
let eps = thresholds::machine_epsilon::<T>();
let eighth_root = T::ONE.div(eps).sqrt().sqrt().sqrt();
let (ten, hundred) = (T::from_count(10), T::from_count(100));
let capped = if eighth_root < hundred {
eighth_root
} else {
hundred
};
let tolmul = if capped > ten { capped } else { ten };
let tol = tolmul.mul(eps);
let hundredth = tol.div(T::from_count(100));
let bound = if eps > hundredth { eps } else { hundredth };
let n = 5usize;
let outside = T::from_count(1000);
let cutoff = bound.div(T::from_count(n).mul(tol));
let x = cutoff.add(cutoff);
assert!(
x < T::ONE,
"construction invariant: x must stay below the block's own scale of 1"
);
let mut d = vec![outside, T::ONE, T::ONE, x, outside];
let mut e = vec![outside, T::ZERO, T::ZERO, outside];
let deflation = Deflation::new(&d, &e, n);
let block = Oriented::<T, Down>::new(&mut d, &mut e, 1, 3);
assert_eq!(
block.largest_entry(),
T::ONE,
"SMAX must come from the block [1, 3], not the outside entries"
);
assert!(
!deflation.shift_ruins_accuracy(&block),
"a whole-bidiagonal SMAX would fire the zero-shift test regardless of x; \
the block's own SMAX of 1 must not, at this construction's x"
);
}
#[test]
fn zero_shift_test_scopes_smax_to_the_active_block_across_scalar_types() {
use eunomia::{Bf16, F16};
zero_shift_test_scopes_smax_to_the_active_block::<f32>();
zero_shift_test_scopes_smax_to_the_active_block::<f64>();
zero_shift_test_scopes_smax_to_the_active_block::<F16>();
zero_shift_test_scopes_smax_to_the_active_block::<Bf16>();
}
fn largest_entry_is_dominated_by_a_reachable_in_block_superdiagonal<T: RealScalar>() {
use super::chase::{Down, Oriented};
let (outside_d0, outside_d4) = (T::from_count(7), T::from_count(9).neg());
let one = T::ONE;
let mut d = vec![outside_d0, one, one, one, outside_d4];
let mut e = vec![
T::ZERO,
T::from_count(2).div(T::from_count(10)),
T::from_count(5),
T::ZERO,
];
let block = Oriented::<T, Down>::new(&mut d, &mut e, 1, 3);
assert_eq!(
block.largest_entry(),
T::from_count(5),
"SMAX must be the in-block superdiagonal e[2], not the in-block d's"
);
}
#[test]
fn largest_entry_is_dominated_by_a_reachable_in_block_superdiagonal_across_scalar_types() {
use eunomia::{Bf16, F16};
largest_entry_is_dominated_by_a_reachable_in_block_superdiagonal::<f32>();
largest_entry_is_dominated_by_a_reachable_in_block_superdiagonal::<f64>();
largest_entry_is_dominated_by_a_reachable_in_block_superdiagonal::<F16>();
largest_entry_is_dominated_by_a_reachable_in_block_superdiagonal::<Bf16>();
}