use super::shift::KEXSH;
use super::{at, deflation_floor};
use crate::domain::real::RealScalar;
pub(super) fn run_floor<T: RealScalar>(h: &[T], n: usize) -> T {
use crate::application::linalg::thresholds;
let absolute = deflation_floor::<T>();
let largest = h
.iter()
.fold(T::ZERO, |acc, &v| if v.abs() > acc { v.abs() } else { acc });
let Some(exponent) = largest.binary_exponent() else {
return absolute;
};
let eps = thresholds::machine_epsilon::<T>();
let smlnum = thresholds::safe_min::<T>()
.div(eps)
.scale_binary(thresholds::ceil_log2_count(n));
let relative = if smlnum < eps { smlnum } else { eps };
let relative = relative.scale_binary(exponent - thresholds::ceil_log2_count(n));
if relative > absolute {
relative
} else {
absolute
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(super) enum Criterion {
AhuesTisseur,
Neighbourhood,
}
pub(super) const STALLED: usize = 2 * KEXSH;
pub(super) fn iteration_cap(n: usize) -> usize {
30 * n.max(10)
}
pub(super) fn local_scale<T: RealScalar>(h: &[T], n: usize, k: usize) -> T {
let diagonal = at(h, k - 1, k - 1, n).abs().add(at(h, k, k, n).abs());
if diagonal != T::ZERO {
return diagonal;
}
neighbours(h, n, k)
}
pub(super) fn neighbourhood_scale<T: RealScalar>(h: &[T], n: usize, k: usize) -> T {
at(h, k - 1, k - 1, n)
.abs()
.add(at(h, k, k, n).abs())
.add(neighbours(h, n, k))
}
fn neighbours<T: RealScalar>(h: &[T], n: usize, k: usize) -> T {
let below = if k >= 2 {
at(h, k - 1, k - 2, n).abs()
} else {
T::ZERO
};
let above = if k + 1 < n {
at(h, k + 1, k, n).abs()
} else {
T::ZERO
};
below.add(above)
}
pub(super) fn negligible_subdiagonal<T: RealScalar>(
h: &[T],
n: usize,
k: usize,
(ulp, floor): (T, T),
criterion: Criterion,
) -> bool {
let sub = at(h, k, k - 1, n).abs();
if sub <= floor {
return true;
}
if criterion == Criterion::Neighbourhood {
return sub <= ulp.mul(neighbourhood_scale(h, n, k));
}
if sub > ulp.mul(local_scale(h, n, k)) {
return false;
}
let sup = at(h, k - 1, k, n).abs();
let (ab, ba) = if sub > sup { (sub, sup) } else { (sup, sub) };
let hkk = at(h, k, k, n).abs();
let gap = at(h, k - 1, k - 1, n).sub(at(h, k, k, n)).abs();
let (aa, bb) = if hkk > gap { (hkk, gap) } else { (gap, hkk) };
let s = aa.add(ab);
let relative = ulp.mul(bb.mul(aa.div(s)));
ba.mul(ab.div(s)) <= if floor > relative { floor } else { relative }
}
#[cfg(test)]
mod tests {
use super::{negligible_subdiagonal, Criterion};
use crate::application::linalg::thresholds;
use crate::domain::real::RealScalar;
use eunomia::{Bf16, F16};
fn threshold_is_two_ulp<T: RealScalar>() {
let ulp = thresholds::machine_epsilon::<T>();
let floor = thresholds::safe_min::<T>();
let skew = |delta: T| {
let mut h = vec![T::ZERO; 16];
for (k, value) in [(1, T::ONE), (2, delta), (3, T::ONE)] {
h[k * 4 + k - 1] = value;
h[(k - 1) * 4 + k] = value.neg();
}
h
};
let two_ulp = ulp.add(ulp);
let at_threshold = skew(two_ulp);
let above = skew(two_ulp.add(two_ulp.mul(ulp)));
let test = |h: &[T], criterion| negligible_subdiagonal(h, 4, 2, (ulp, floor), criterion);
let label = core::any::type_name::<T>();
assert!(test(&at_threshold, Criterion::Neighbourhood), "{label}");
assert!(!test(&at_threshold, Criterion::AhuesTisseur), "{label}");
assert!(!test(&above, Criterion::Neighbourhood), "{label}");
}
#[test]
fn neighbourhood_test_deflates_a_tie_ahues_tisseur_keeps() {
threshold_is_two_ulp::<f64>();
threshold_is_two_ulp::<f32>();
threshold_is_two_ulp::<F16>();
threshold_is_two_ulp::<Bf16>();
}
}