use super::chase::{Chase, Down, Up};
use super::rotation::TransposedFactors;
use super::sweep::{qr_iterate, SweepWindows};
use super::tests::check_bidiagonal;
use super::zero_shift::zero_shift_sweep;
use super::RealScalar;
use crate::application::linalg::thresholds;
use crate::domain::rng::Xorshift64;
use eunomia::RealField;
const REFERENCE_WIDTH: f64 = 2.0 * f64::EPSILON;
fn count_below(d: &[f64], e: &[f64], x: f64) -> usize {
let off_diagonal = d
.iter()
.zip(e.iter().map(Some).chain([None]))
.flat_map(|(&di, ei)| [Some(di), ei.copied()])
.flatten();
let mut q = -x;
let mut negatives = usize::from(q < 0.0);
for b in off_diagonal {
if q == 0.0 {
q = -f64::MIN_POSITIVE;
}
q = (0.0 - b * b / q) - x;
negatives += usize::from(q < 0.0);
}
negatives - d.len()
}
fn reference(d: &[f64], e: &[f64]) -> Vec<f64> {
let bound = 2.0 * d.iter().chain(e).map(|v| v.abs()).sum::<f64>();
(0..d.len())
.map(|j| {
let (mut lo, mut hi) = (bound * f64::MIN_POSITIVE, bound);
while hi - lo > REFERENCE_WIDTH * hi {
let mid = (lo * hi).sqrt();
if count_below(d, e, mid) > j {
hi = mid;
} else {
lo = mid;
}
}
hi
})
.collect()
}
fn reference_error(n: usize) -> f64 {
f64::from(u32::try_from(6 * n).expect("invariant: test orders fit in u32")) * f64::EPSILON
+ REFERENCE_WIDTH
}
fn graded<T: RealScalar>(
rng: &mut Xorshift64,
k: usize,
span: f64,
bottom_heavy: bool,
) -> (Vec<f64>, Vec<f64>) {
let step = span / f64::from(u32::try_from(k - 1).expect("invariant: small order"));
let binade = |i: usize| {
let from_large = if bottom_heavy { k - 1 - i } else { i };
-step * f64::from(u32::try_from(from_large).expect("invariant: small order"))
};
let mut round =
|exponent: f64| T::from_f64((1.0 + rng.next_unit_f64()) * exponent.exp2()).to_f64();
let mut d = Vec::with_capacity(k);
let mut e = Vec::with_capacity(k - 1);
for i in 0..k {
let magnitude = round(binade(i));
d.push(if i % 3 == 1 { -magnitude } else { magnitude });
if i + 1 < k {
e.push(round(0.5 * (binade(i) + binade(i + 1))));
}
}
(d, e)
}
fn span<T: RealScalar + RealField>() -> f64 {
let precision = -<T as RealField>::EPSILON.to_f64().log2();
let range = -thresholds::safe_min::<T>().to_f64().log2();
(2.0 * precision).min(range - precision)
}
fn zero_shift_bound(n: usize, eps: f64) -> f64 {
let n = f64::from(u32::try_from(n).expect("invariant: small order"));
let omega = 69.0 * n * n * eps;
assert!(omega < 1.0, "Theorem 6 needs 69n²ε < 1");
omega / (1.0 - omega)
}
fn assert_relative(got: &[f64], d: &[f64], e: &[f64], bound: f64, context: &str) {
let want = reference(d, e);
let mut got = got.iter().map(|x| x.abs()).collect::<Vec<_>>();
got.sort_by(f64::total_cmp);
for (g, w) in got.iter().zip(&want) {
let relative = (g - w).abs() / w;
assert!(
relative <= bound,
"{context}: σ {g:e} vs {w:e}, relative {relative:e} > {bound:e}; d {d:?} e {e:?}"
);
}
}
fn one_sweep<T: RealScalar + RealField, C: Chase>(d0: &[f64], e0: &[f64]) {
let k = d0.len();
let mut d: Vec<T> = d0.iter().map(|&x| T::from_f64(x)).collect();
let mut e: Vec<T> = e0
.iter()
.map(|&x| T::from_f64(x))
.chain([T::ZERO])
.collect();
let before = reference(d0, e0);
zero_shift_sweep::<T, false, C>(
&mut d,
&mut e,
0,
k - 1,
&mut TransposedFactors::none(),
SweepWindows::<T>::new().rotation,
);
let swept_d: Vec<f64> = d.iter().map(|x| x.to_f64()).collect();
let swept_e: Vec<f64> = e[..k - 1].iter().map(|x| x.to_f64()).collect();
let eps = <T as RealField>::EPSILON.to_f64();
let bound = zero_shift_bound(k, eps) + 2.0 * reference_error(k);
assert_relative(&before, &swept_d, &swept_e, bound, "one zero-shift sweep");
}
fn zero_shift_sweep_is_relatively_accurate<T: RealScalar + RealField>() {
let mut rng = Xorshift64::new(0x5eed_b1d1);
for case in 0..240 {
let k = 3 + case % 6;
for bottom_heavy in [false, true] {
let (d, e) = graded::<T>(&mut rng, k, span::<T>(), bottom_heavy);
one_sweep::<T, Down>(&d, &e);
one_sweep::<T, Up>(&d, &e);
}
}
}
#[test]
fn zero_shift_sweep_keeps_relative_accuracy_in_both_directions() {
zero_shift_sweep_is_relatively_accurate::<f32>();
zero_shift_sweep_is_relatively_accurate::<f64>();
}
fn reduction_bound<T: RealScalar + RealField>(k: usize, sweeps: usize) -> f64 {
let eps = <T as RealField>::EPSILON.to_f64();
let machine = thresholds::machine_epsilon::<T>().to_f64();
let tolmul = machine.powf(-0.125).clamp(10.0, 100.0);
let tol = tolmul * machine;
let order = f64::from(u32::try_from(k).expect("invariant: small order"));
let shifted = 16.0 * order.powf(2.5) * (tol / machine.max(tol / 100.0)) * eps;
let per_sweep = zero_shift_bound(k, eps).max(shifted);
let split = order * tol / core::f64::consts::SQRT_2;
let sweeps = i32::try_from(sweeps).expect("invariant: sweep count fits in i32");
let splits = i32::try_from(k - 1).expect("invariant: small order");
(1.0 + per_sweep).powi(sweeps) * (1.0 + split).powi(splits) * (1.0 + zero_shift_bound(2, eps))
- 1.0
+ reference_error(k)
}
fn sweep_ceiling<T: RealScalar>(k: usize, step: f64) -> usize {
let machine = thresholds::machine_epsilon::<T>().to_f64();
let tol = machine.powf(-0.125).clamp(10.0, 100.0) * machine;
let per_split = ((step / 2.0 + 2.0 - tol.log2()) / (2.0 * (step - 1.0))).ceil();
let per_split = u32::try_from(per_split as i64).expect("invariant: a few sweeps per split");
(k - 1) * per_split as usize
}
fn step<T: RealScalar + RealField>(k: usize) -> f64 {
span::<T>() / f64::from(u32::try_from(k - 1).expect("invariant: small order"))
}
fn iterate<T: RealScalar>(d0: &[f64], e0: &[f64]) -> (Vec<f64>, usize) {
let mut d: Vec<T> = d0.iter().map(|&x| T::from_f64(x)).collect();
let mut e: Vec<T> = e0
.iter()
.map(|&x| T::from_f64(x))
.chain([T::ZERO])
.collect();
let counts = qr_iterate::<T, false>(&mut d, &mut e, d0.len(), &mut TransposedFactors::none())
.expect("a graded bidiagonal converges");
let sweeps = counts.total();
let mut sigma: Vec<f64> = d.iter().map(|x| x.to_f64().abs()).collect();
sigma.sort_by(f64::total_cmp);
(sigma, sweeps)
}
fn graded_reductions_are_relatively_accurate<T: RealScalar + RealField>() {
let mut rng = Xorshift64::new(0x0b07_70e5);
for case in 0..600 {
let k = 3 + case % 6;
for bottom_heavy in [true, false] {
let (d0, e0) = graded::<T>(&mut rng, k, span::<T>(), bottom_heavy);
let (got, sweeps) = iterate::<T>(&d0, &e0);
assert!(
sweeps <= sweep_ceiling::<T>(k, step::<T>(k)),
"{sweeps} iterations at order {k}; d {d0:?} e {e0:?}"
);
let bound = reduction_bound::<T>(k, sweeps);
assert_relative(&got, &d0, &e0, bound, "graded reduction");
}
}
}
#[test]
fn graded_bidiagonals_keep_relative_accuracy_at_either_end() {
graded_reductions_are_relatively_accurate::<f32>();
graded_reductions_are_relatively_accurate::<f64>();
}
#[test]
fn bottom_heavy_iteration_reconstructs_its_input() {
fn check<T: RealScalar + RealField>() {
let mut rng = Xorshift64::new(0x00c0_ffee);
for k in 3..=8 {
let (d, e) = graded::<T>(&mut rng, k, span::<T>(), true);
let mut expected = reference(&d, &e);
expected.reverse();
check_bidiagonal::<T>(&d, &e, &expected);
}
}
check::<f32>();
check::<f64>();
}
fn composite_blocks_are_relatively_accurate<T: RealScalar + RealField>() {
let mut rng = Xorshift64::new(0x00b1_0c55);
for case in 0..300 {
let (upper, lower) = (3 + case % 4, 3 + (case / 4) % 4);
let (du, eu) = graded::<T>(&mut rng, upper, span::<T>(), true);
let (dl, el) = graded::<T>(&mut rng, lower, span::<T>(), false);
let d0: Vec<f64> = du.iter().chain(&dl).copied().collect();
let e0: Vec<f64> = eu.iter().chain(&[0.0]).chain(&el).copied().collect();
let (got, sweeps) = iterate::<T>(&d0, &e0);
let ceiling = sweep_ceiling::<T>(upper, step::<T>(upper))
+ sweep_ceiling::<T>(lower, step::<T>(lower));
assert!(sweeps <= ceiling, "{sweeps} > {ceiling}; d {d0:?} e {e0:?}");
let bound = reduction_bound::<T>(upper + lower, sweeps);
assert_relative(&got, &d0, &e0, bound, "composite reduction");
}
}
#[test]
fn each_block_takes_its_own_chase_direction() {
composite_blocks_are_relatively_accurate::<f32>();
composite_blocks_are_relatively_accurate::<f64>();
}
fn large_over_small_block_never_exceeds_running_each_alone<T: RealScalar + RealField>() {
let mut rng = Xorshift64::new(0x1a46_e5ca_b10c);
let mild_span = 3.0;
let scale = 2f64.powi(22); for &k in &[4usize, 5] {
let (du, eu) = graded::<T>(&mut rng, k, mild_span, true);
let (dl, el) = graded::<T>(&mut rng, k, mild_span, false);
let du: Vec<f64> = du.iter().map(|x| x * scale).collect();
let eu: Vec<f64> = eu.iter().map(|x| x * scale).collect();
let (_, upper_alone) = iterate::<T>(&du, &eu);
let (_, lower_alone) = iterate::<T>(&dl, &el);
let d0: Vec<f64> = du.iter().chain(&dl).copied().collect();
let e0: Vec<f64> = eu.iter().chain(&[0.0]).chain(&el).copied().collect();
let (got, sweeps) = iterate::<T>(&d0, &e0);
let ceiling = upper_alone + lower_alone;
assert!(
sweeps <= ceiling,
"k={k}: composite took {sweeps} sweeps, alone-sum is {ceiling} \
(upper {upper_alone}, lower {lower_alone}); d {d0:?} e {e0:?}"
);
let bound = reduction_bound::<T>(2 * k, sweeps);
assert_relative(
&got,
&d0,
&e0,
bound,
"large-over-small composite reduction",
);
}
}
#[test]
fn large_over_small_block_matches_its_blocks_run_in_isolation() {
large_over_small_block_never_exceeds_running_each_alone::<f32>();
large_over_small_block_never_exceeds_running_each_alone::<f64>();
}
fn reflection_is_a_mirror<T: RealScalar + RealField>() {
let mut rng = Xorshift64::new(0x0b07_70e5);
for case in 0..1200 {
let k = 3 + case % 6;
let span = if case % 4 < 2 {
span::<T>()
} else {
2.0 + f64::from(u32::try_from(case % 11).expect("invariant: small"))
};
let (d0, e0) = graded::<T>(&mut rng, k, span, case % 2 == 0);
let dr: Vec<f64> = d0.iter().rev().copied().collect();
let er: Vec<f64> = e0.iter().rev().copied().collect();
let (sigma, sweeps) = iterate::<T>(&d0, &e0);
let (mirrored, mirrored_sweeps) = iterate::<T>(&dr, &er);
assert_eq!(sigma, mirrored, "d {d0:?} e {e0:?}");
assert_eq!(sweeps, mirrored_sweeps, "d {d0:?} e {e0:?}");
}
}
#[test]
fn reflected_input_iterates_as_the_mirror_image() {
reflection_is_a_mirror::<f32>();
reflection_is_a_mirror::<f64>();
}