use xingo_sparse::{Col, CscMatrix, CsrMatrix, Row};
use crate::dd::DoubleDouble;
use crate::eft::{two_prod, two_sum};
use crate::interval::Interval;
use crate::kernels;
#[derive(Clone, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub enum VerifyError {
Dimension {
expected: usize,
got: usize,
},
}
impl core::fmt::Display for VerifyError {
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
match self {
Self::Dimension { expected, got } => {
write!(f, "dimension mismatch: expected {expected}, got {got}")
}
}
}
}
impl core::error::Error for VerifyError {}
fn dimension(expected: usize, got: usize) -> Result<(), VerifyError> {
if got == expected {
Ok(())
} else {
Err(VerifyError::Dimension { expected, got })
}
}
fn enclosure(r: DoubleDouble, beta: f64) -> Interval {
let known = beta.is_finite() && beta >= 0.0 && r.hi().is_finite() && r.lo().is_finite();
let x = if known {
Interval::mid_rad(r.lo(), beta) + r.hi()
} else {
Interval::ENTIRE
};
debug_assert!(
x.check_invariants().is_ok() && !x.is_empty(),
"V2: {x:?} from r = {r:?}, β = {beta:e}"
);
x
}
fn vec_sum(w: &mut Vec<f64>) -> Option<f64> {
let Some(&first) = w.first() else {
return Some(0.0);
};
let mut sigma = first;
for j in 1..w.len() {
let (s, e) = two_sum(sigma, w[j]);
if !(s.is_finite() && e.is_finite()) {
return None;
}
w[j - 1] = e;
sigma = s;
}
w.pop();
Some(sigma)
}
const FLOOR: f64 = 6.0 * f64::MIN_POSITIVE * (1.0 + 4.0 * f64::EPSILON);
fn distilled(p: &[f64], q: &[f64], w: &mut Vec<f64>) -> Option<Interval> {
const MAX_TERMS: u64 = 1 << 52;
w.clear();
for (&pj, &qj) in p.iter().zip(q) {
let (pi, eps) = two_prod(pj, qj);
if !(pi.is_finite() && eps.is_finite()) {
return None;
}
w.push(pi);
w.push(eps);
}
let sigma_1 = vec_sum(w)?;
let sigma_2 = vec_sum(w)?;
let (mut t, mut a) = (0.0_f64, 0.0_f64);
for &v in w.iter() {
t += v;
a += v.abs();
}
let m = w.len().max(1) - 1;
if u64::try_from(m).map_or(true, |m| m >= MAX_TERMS) || !(t.is_finite() && a.is_finite()) {
return None;
}
#[allow(clippy::cast_precision_loss)] let mu = m as f64 * U;
let delta = Interval::point(mu) / (1.0 - Interval::point(2.0 * mu));
let beta = upper((delta * Interval::point(a) + Interval::point(FLOOR)).sup());
if !beta.is_finite() {
return None;
}
let (s, tau) = two_sum(sigma_1, sigma_2);
if !(s.is_finite() && tau.is_finite()) {
return None;
}
Some(Interval::mid_rad(t, beta) + tau + s)
}
fn rows(
a: &CsrMatrix<f64>,
distil: bool,
mut fill: impl FnMut(usize, &[u32], &[f64], &mut Vec<f64>, &mut Vec<f64>),
) -> Vec<Interval> {
let (mut p, mut q, mut w) = (Vec::new(), Vec::new(), Vec::new());
(0..a.n_rows())
.map(|i| {
p.clear();
q.clear();
let (cols, vals) = a.row(Row::from_usize(i));
fill(i, cols, vals, &mut p, &mut q); let (r, beta) = kernels::dot2_err(&p, &q); let x = enclosure(r, beta); if !distil {
return x;
}
match distilled(&p, &q, &mut w) {
None => x,
Some(narrow) => {
let y = x.intersection(narrow);
debug_assert!(
!y.is_empty() && y.is_subset_of(x),
"V1/V3: {x:?} ∩ {narrow:?} in row {i}"
);
if y.is_empty() { x } else { y }
}
}
})
.collect()
}
pub fn residual(a: &CsrMatrix<f64>, x: &[f64], b: &[f64]) -> Result<Vec<Interval>, VerifyError> {
dimension(a.n_cols(), x.len())?;
dimension(a.n_rows(), b.len())?;
Ok(rows(a, false, |i, cols, vals, p, q| {
p.extend_from_slice(vals);
q.extend(cols.iter().map(|&j| x[j as usize]));
p.push(-1.0);
q.push(b[i]);
}))
}
pub fn residual_of_dd(
a: &CsrMatrix<f64>,
x: &[DoubleDouble],
b: &[f64],
) -> Result<Vec<Interval>, VerifyError> {
dimension(a.n_cols(), x.len())?;
dimension(a.n_rows(), b.len())?;
Ok(rows(a, true, |i, cols, vals, p, q| {
p.extend_from_slice(vals);
q.extend(cols.iter().map(|&j| x[j as usize].hi()));
p.extend_from_slice(vals);
q.extend(cols.iter().map(|&j| x[j as usize].lo()));
p.push(-1.0);
q.push(b[i]);
}))
}
pub fn residual_csc(
a: &CscMatrix<f64>,
x: &[f64],
b: &[f64],
) -> Result<Vec<Interval>, VerifyError> {
dimension(a.n_cols(), x.len())?;
dimension(a.n_rows(), b.len())?;
residual(&a.to_csr(), x, b)
}
pub fn residual_dd(
a: &CsrMatrix<f64>,
x: &[DoubleDouble],
b: &[f64],
) -> Result<Vec<DoubleDouble>, VerifyError> {
dimension(a.n_cols(), x.len())?;
dimension(a.n_rows(), b.len())?;
let mut gathered = Vec::new();
Ok(b.iter()
.enumerate()
.map(|(i, &bi)| {
let (cols, vals) = a.row(Row::from_usize(i));
gathered.clear();
gathered.extend(cols.iter().map(|&j| x[j as usize]));
DoubleDouble::from_f64(bi) - kernels::dot_mixed(&gathered, vals)
})
.collect())
}
#[must_use]
pub fn norm_inf_bound(r: &[Interval]) -> f64 {
r.iter().fold(0.0, |norm: f64, x| {
if x.is_empty() {
f64::INFINITY
} else {
norm.max(x.mag())
}
})
}
pub fn activity(a: &CsrMatrix<f64>, x: &[f64]) -> Result<Vec<Interval>, VerifyError> {
dimension(a.n_cols(), x.len())?;
Ok(rows(a, false, |_, cols, vals, p, q| {
p.extend_from_slice(vals);
q.extend(cols.iter().map(|&j| x[j as usize]));
}))
}
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct PolishOptions {
pub tol: f64,
pub min_progress: f64,
pub max_iter: u32,
}
impl Default for PolishOptions {
fn default() -> Self {
Self {
tol: f64::from_bits((1023 - 90) << 52),
min_progress: 0.5,
max_iter: 10,
}
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub enum PolishStop {
Converged,
Stagnated,
IterationLimit,
NotFinite,
}
#[derive(Clone, Debug, PartialEq)]
#[non_exhaustive]
pub struct PolishReport {
pub stop: PolishStop,
pub iterations: u32,
pub residual_before: f64,
pub residual_after: f64,
}
fn norm_inf(v: &[DoubleDouble]) -> f64 {
v.iter().fold(0.0, |norm: f64, c| {
let h = c.hi().abs();
if h.is_nan() || norm.is_nan() {
f64::NAN
} else {
norm.max(h)
}
})
}
const U: f64 = 0.5 * f64::EPSILON;
fn rows_converged(
a: &CsrMatrix<f64>,
x: &[DoubleDouble],
b: &[f64],
r: &[DoubleDouble],
tol: f64,
) -> bool {
r.iter().zip(b).enumerate().all(|(i, (ri, bi))| {
let (cols, vals) = a.row(Row::from_usize(i));
let mut s = bi.abs();
for (&j, v) in cols.iter().zip(vals) {
s += v.abs() * x[j as usize].hi().abs();
}
#[allow(clippy::cast_precision_loss)] let deflate = 1.0 - (2 * cols.len() + 10) as f64 * U;
let t = tol * s * deflate;
t.is_finite() && ri.hi().abs() <= t
})
}
pub fn polish(
a: &CsrMatrix<f64>,
b: &[f64],
x: &mut [DoubleDouble],
solve: &mut dyn FnMut(&mut [f64]),
opts: &PolishOptions,
) -> Result<PolishReport, VerifyError> {
dimension(a.n_cols(), x.len())?;
dimension(a.n_rows(), b.len())?;
dimension(a.n_rows(), a.n_cols())?;
let mut previous: Vec<DoubleDouble> = x.to_vec();
let mut s = vec![0.0; b.len()];
let mut iterations = 0_u32;
let mut nu_prev = f64::INFINITY;
let mut nu_first = f64::NAN;
let (stop, nu) = loop {
let r = residual_dd(a, x, b)?;
let nu = norm_inf(&r);
if iterations == 0 {
nu_first = nu;
}
if !nu.is_finite() || nu > nu_prev {
let stop = if nu.is_finite() {
PolishStop::Stagnated } else {
PolishStop::NotFinite };
if iterations > 0 {
x.copy_from_slice(&previous);
iterations -= 1;
break (stop, nu_prev);
}
break (stop, nu);
}
if rows_converged(a, x, b, &r, opts.tol) {
break (PolishStop::Converged, nu); }
if iterations > 0 && nu > opts.min_progress * nu_prev {
break (PolishStop::Stagnated, nu); }
if iterations >= opts.max_iter {
break (PolishStop::IterationLimit, nu); }
for (si, ri) in s.iter_mut().zip(&r) {
*si = ri.hi();
}
solve(&mut s);
if !s.iter().all(|d| d.is_finite()) {
break (PolishStop::NotFinite, nu);
}
previous.copy_from_slice(x);
for (xi, &di) in x.iter_mut().zip(&s) {
#[allow(clippy::assign_op_pattern)]
{
*xi = *xi + di;
}
}
nu_prev = nu;
iterations += 1;
};
debug_assert!(
!nu_first.is_finite() || nu <= nu_first,
"P1: the residual grew from {nu_first:e} to {nu:e}"
);
Ok(PolishReport {
stop,
iterations,
residual_before: nu_first,
residual_after: nu,
})
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct ForwardErrorOptions {
pub refine_rows: bool,
}
impl Default for ForwardErrorOptions {
fn default() -> Self {
Self { refine_rows: true }
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub enum ForwardErrorOutcome {
Certified,
NotContracting,
NotFinite,
}
#[derive(Clone, Debug, PartialEq)]
#[non_exhaustive]
pub struct ForwardErrorBound {
pub outcome: ForwardErrorOutcome,
pub norm_inf: f64,
pub componentwise: Vec<f64>,
pub contraction: f64,
pub solves: usize,
}
impl ForwardErrorBound {
pub fn is_certified(&self) -> bool {
self.outcome == ForwardErrorOutcome::Certified
}
fn refused(outcome: ForwardErrorOutcome, n: usize, contraction: f64, solves: usize) -> Self {
Self {
outcome,
norm_inf: f64::INFINITY,
componentwise: vec![f64::INFINITY; n],
contraction,
solves,
}
}
fn check_invariants(&self) -> Result<(), &'static str> {
let finite = self.norm_inf.is_finite();
if self.is_certified() {
if !(finite && self.norm_inf >= 0.0) {
return Err("E3: a certificate with an infinite or negative ε");
}
if !(0.0..1.0).contains(&self.contraction) {
return Err("E3: a certificate with α outside [0, 1)");
}
if !self
.componentwise
.iter()
.all(|&c| c >= 0.0 && c <= self.norm_inf)
{
return Err("E3: some ε_p outside [0, ε]");
}
} else if finite || self.componentwise.iter().any(|c| c.is_finite()) {
return Err("E3: a finite bound without a certificate");
}
Ok(())
}
}
fn upper(x: f64) -> f64 {
if x.is_nan() { f64::INFINITY } else { x }
}
fn kronecker(p: usize, q: usize) -> f64 {
if p == q { 1.0 } else { 0.0 }
}
fn row_sets(
a: &CsrMatrix<f64>,
p: usize,
(h, l): (&[f64], &[f64]),
mark: &mut [bool],
support: &mut Vec<usize>,
cols: &mut Vec<usize>,
) {
support.clear();
cols.clear();
for (i, (&hi, &li)) in h.iter().zip(l).enumerate() {
if hi != 0.0 || li != 0.0 {
support.push(i);
for &q in a.row(Row::from_usize(i)).0 {
let q = q as usize;
if !mark[q] {
mark[q] = true;
cols.push(q);
}
}
}
}
if !mark[p] {
mark[p] = true;
cols.push(p);
}
for &q in cols.iter() {
mark[q] = false;
}
}
pub fn forward_error_bound(
a: &CsrMatrix<f64>,
r: &[Interval],
solve_transpose: &mut dyn FnMut(&mut [f64]),
opts: &ForwardErrorOptions,
) -> Result<ForwardErrorBound, VerifyError> {
use ForwardErrorOutcome::{Certified, NotContracting, NotFinite};
dimension(a.n_rows(), a.n_cols())?;
let n = a.n_rows();
dimension(n, r.len())?;
if r.iter().any(|x| x.is_empty()) {
return Ok(ForwardErrorBound::refused(NotFinite, n, 0.0, 0));
}
let bound =
forward_error_rows(a, r, solve_transpose, opts.refine_rows).unwrap_or_else(|refusal| {
let (outcome, alpha, solves) = refusal;
ForwardErrorBound::refused(outcome, n, alpha, solves)
});
debug_assert!(
bound.check_invariants().is_ok(),
"{:?}: {bound:?}",
bound.check_invariants()
);
debug_assert!(n > 0 || bound.outcome == Certified);
debug_assert!(bound.outcome != NotContracting || bound.contraction >= 1.0);
Ok(bound)
}
#[allow(clippy::neg_cmp_op_on_partial_ord)]
fn forward_error_rows(
a: &CsrMatrix<f64>,
r: &[Interval],
solve_transpose: &mut dyn FnMut(&mut [f64]),
refine_rows: bool,
) -> Result<ForwardErrorBound, (ForwardErrorOutcome, f64, usize)> {
use ForwardErrorOutcome::{Certified, NotContracting, NotFinite};
let n = a.n_rows();
let csc = a.to_csc();
let (mut h, mut l, mut d) = (vec![0.0; n], vec![0.0; n], vec![0.0; n]);
let mut mark = vec![false; n];
let (mut support, mut cols) = (Vec::new(), Vec::new());
let (mut pp, mut qq) = (Vec::new(), Vec::new());
let (mut rho, mut g) = (vec![0.0; n], vec![0.0; n]);
let mut alpha = 0.0_f64;
let mut solves = 0_usize;
for p in 0..n {
h.fill(0.0);
l.fill(0.0);
h[p] = 1.0;
solve_transpose(&mut h);
solves += 1;
if !h.iter().all(|v| v.is_finite()) {
return Err((NotFinite, alpha, solves));
}
let mut refined = false;
if refine_rows {
row_sets(a, p, (&h, &l), &mut mark, &mut support, &mut cols);
d.fill(0.0);
for &q in &cols {
let (rows, vals) = csc.col(Col::from_usize(q));
qq.clear();
qq.extend(rows.iter().map(|&i| h[i as usize]));
d[q] = (DoubleDouble::from_f64(kronecker(p, q)) - kernels::dot2(vals, &qq)).hi();
}
solve_transpose(&mut d);
solves += 1;
if d.iter()
.zip(&h)
.all(|(&di, &hi)| di.is_finite() && (hi + di).is_finite())
{
refined = true;
for ((hi, li), &di) in h.iter_mut().zip(l.iter_mut()).zip(&d) {
let s = DoubleDouble::from_f64(*hi) + di;
(*hi, *li) = (s.hi(), s.lo());
}
}
}
debug_assert!(
h.iter().chain(&l).all(|v| v.is_finite()),
"(o): a non-finite component in row {p} of R"
);
row_sets(a, p, (&h, &l), &mut mark, &mut support, &mut cols);
let mut sum = Interval::ZERO;
for &q in &cols {
let (rows, vals) = csc.col(Col::from_usize(q));
pp.clear();
qq.clear();
pp.extend_from_slice(vals);
qq.extend(rows.iter().map(|&i| h[i as usize]));
if refined {
pp.extend_from_slice(vals);
qq.extend(rows.iter().map(|&i| l[i as usize]));
}
pp.push(-1.0);
qq.push(kronecker(p, q));
let (s, beta) = kernels::dot2_err(&pp, &qq);
sum += enclosure(s, beta).mag();
}
rho[p] = upper(sum.sup());
let mut acc = Interval::ZERO;
for &i in &support {
for y in [h[i], l[i]] {
if y != 0.0 {
acc += r[i] * y;
}
}
}
g[p] = upper(acc.mag());
alpha = alpha.max(rho[p]);
if !(alpha < 1.0) {
return Err((NotContracting, alpha, solves));
}
}
let gamma = g.iter().fold(0.0_f64, |m, &v| m.max(v));
if !gamma.is_finite() {
return Err((NotFinite, alpha, solves));
}
let eps = upper((Interval::point(gamma) / (1.0 - Interval::point(alpha))).sup());
if !eps.is_finite() {
return Err((NotFinite, alpha, solves));
}
let componentwise = g
.iter()
.zip(&rho)
.map(|(&gp, &rp)| upper((Interval::point(gp) + Interval::point(rp) * eps).sup()).min(eps))
.collect();
Ok(ForwardErrorBound {
outcome: Certified,
norm_inf: eps,
componentwise,
contraction: alpha,
solves,
})
}
#[cfg(test)]
#[allow(clippy::disallowed_methods)] #[allow(clippy::float_cmp)] mod tests {
use super::*;
type Dd = DoubleDouble;
fn small() -> CsrMatrix<f64> {
CsrMatrix::from_raw_parts(2, vec![0, 2, 4], vec![0, 1, 0, 1], vec![2.0, 1.0, 1.0, 3.0])
.expect("a valid matrix")
}
#[test]
fn exact_data_give_point_like_residuals() {
let a = small();
let r = residual(&a, &[1.0, 2.0], &[4.0, 6.0]).unwrap();
assert!(r[0].contains(0.0) && r[0].width() < 1e-300);
assert!(r[1].contains(1.0) && r[1].width() < 1e-15);
assert!(r[1].certainly_within(1.0 + 1e-15) && !r[1].certainly_within(0.5));
let s = activity(&a, &[1.0, 2.0]).unwrap();
assert!(s[0].contains(4.0) && s[1].contains(7.0));
assert!(s[1].certainly_le(7.0 + 1e-12) && s[1].certainly_ge(7.0 - 1e-12));
let n = norm_inf_bound(&r);
assert!((1.0..1.0 + 1e-15).contains(&n));
assert_eq!(
residual_csc(&a.to_csc(), &[1.0, 2.0], &[4.0, 6.0]).unwrap(),
r
);
let x = [Dd::from_f64(1.0), Dd::from_f64(2.0)];
assert_eq!(residual_of_dd(&a, &x, &[4.0, 6.0]).unwrap(), r);
assert_eq!(
residual_dd(&a, &x, &[4.0, 6.0]).unwrap(),
vec![Dd::ZERO, Dd::from_f64(-1.0)]
);
}
#[test]
fn a_residual_below_the_f64_grid_is_seen() {
let x = 1.0 + f64::EPSILON;
let a = CsrMatrix::from_raw_parts(1, vec![0, 1], vec![0], vec![x]).unwrap();
let r = residual(&a, &[x], &[1.0 + 2.0 * f64::EPSILON]).unwrap();
let exact = f64::EPSILON * f64::EPSILON;
assert!(r[0].contains(exact) && r[0].certainly_ge(exact * 0.5));
let xd = [Dd::from_sum(1.0, exact)];
let one = CsrMatrix::from_raw_parts(1, vec![0, 1], vec![0], vec![1.0]).unwrap();
let r = residual_of_dd(&one, &xd, &[1.0]).unwrap();
assert!(r[0].contains(exact) && r[0].certainly_ge(exact * 0.5));
}
#[test]
fn failed_hypotheses_claim_nothing() {
let a = small();
for bad in [f64::NAN, f64::INFINITY, f64::NEG_INFINITY] {
let r = residual(&a, &[bad, 1.0], &[0.0, 0.0]).unwrap();
assert_eq!(r, vec![Interval::ENTIRE; 2], "{bad}");
assert_eq!(norm_inf_bound(&r), f64::INFINITY);
let s = activity(&a, &[1.0, bad]).unwrap();
assert_eq!(s, vec![Interval::ENTIRE; 2], "{bad}");
}
let r = residual(&a, &[1e308, 1.0], &[0.0, 0.0]).unwrap();
assert_eq!(r[0], Interval::ENTIRE);
assert!(r[1].contains(1e308) && r[1].width() < 1e293);
let r = residual(&a, &[1.0, 1.0], &[f64::NAN, 0.0]).unwrap();
assert_eq!(r[0], Interval::ENTIRE);
assert!(r[1].contains(4.0));
let r = residual_of_dd(&a, &[Dd::NAN, Dd::ONE], &[0.0, 0.0]).unwrap();
assert_eq!(r, vec![Interval::ENTIRE; 2]);
assert_eq!(norm_inf_bound(&[]), 0.0);
assert_eq!(
norm_inf_bound(&[Interval::ZERO, Interval::EMPTY]),
f64::INFINITY
);
assert_eq!(enclosure(Dd::ONE, f64::NAN), Interval::ENTIRE);
}
#[test]
fn dimensions_are_checked_first() {
let a = small();
let err = |expected, got| VerifyError::Dimension { expected, got };
assert_eq!(residual(&a, &[1.0], &[0.0, 0.0]), Err(err(2, 1)));
assert_eq!(residual(&a, &[1.0, 1.0], &[0.0]), Err(err(2, 1)));
assert_eq!(
residual_csc(&a.to_csc(), &[1.0; 3], &[0.0; 2]),
Err(err(2, 3))
);
assert_eq!(residual_of_dd(&a, &[Dd::ONE], &[0.0; 2]), Err(err(2, 1)));
assert_eq!(residual_dd(&a, &[Dd::ONE; 2], &[0.0; 3]), Err(err(2, 3)));
assert_eq!(activity(&a, &[]), Err(err(2, 0)));
let mut x = [Dd::ONE; 2];
let o = PolishOptions::default();
assert_eq!(polish(&a, &[0.0], &mut x, &mut |_| {}, &o), Err(err(2, 1)));
let wide = CsrMatrix::from_raw_parts(2, vec![0, 2], vec![0, 1], vec![1.0, 1.0]).unwrap();
assert_eq!(
polish(&wide, &[0.0], &mut x, &mut |_| {}, &o),
Err(err(1, 2))
);
}
#[test]
fn errors_are_errors() {
let e: Box<dyn core::error::Error> = Box::new(VerifyError::Dimension {
expected: 3,
got: 2,
});
assert_eq!(e.to_string(), "dimension mismatch: expected 3, got 2");
}
#[test]
fn convergence_is_tested_row_by_row() {
let a = CsrMatrix::from_raw_parts(2, vec![0, 1, 2], vec![0, 1], vec![1e20, 1.0]).unwrap();
let b = [1e20, 1.0];
let mut x = [Dd::ONE, Dd::from_f64(1.0 + 1e-10)];
let mut solve = |s: &mut [f64]| s[0] /= 1e20;
let rep = polish(&a, &b, &mut x, &mut solve, &PolishOptions::default()).unwrap();
assert_eq!((rep.stop, rep.iterations), (PolishStop::Converged, 1));
assert_eq!(x, [Dd::ONE, Dd::ONE]);
let two = CsrMatrix::from_raw_parts(1, vec![0, 1], vec![0], vec![2.0]).unwrap();
let start = [Dd::from_f64(1.0 + f64::EPSILON)];
let loose = PolishOptions {
tol: 0.6 * f64::EPSILON,
..PolishOptions::default()
};
let tight = PolishOptions {
tol: 0.4 * f64::EPSILON,
..PolishOptions::default()
};
let mut x = start;
let rep = polish(&two, &[2.0], &mut x, &mut |s| s[0] /= 2.0, &loose).unwrap();
assert_eq!((rep.stop, rep.iterations), (PolishStop::Converged, 0));
let mut x = start;
let rep = polish(&two, &[2.0], &mut x, &mut |s| s[0] /= 2.0, &tight).unwrap();
assert_eq!((rep.stop, rep.iterations), (PolishStop::Converged, 1));
assert_eq!(x, [Dd::ONE]);
}
#[test]
fn progress_is_measured_in_the_norm() {
let a = CsrMatrix::from_raw_parts(2, vec![0, 1, 2], vec![0, 1], vec![1e20, 1.0]).unwrap();
let b = [1e20, 1.0];
let start = [Dd::from_f64(1.0 + f64::EPSILON), Dd::from_f64(1.5)];
let mut x = start;
let mut solve = |s: &mut [f64]| s[0] = 0.0;
let rep = polish(&a, &b, &mut x, &mut solve, &PolishOptions::default()).unwrap();
assert_eq!((rep.stop, rep.iterations), (PolishStop::Stagnated, 1));
assert_eq!(x, [start[0], Dd::ONE]);
assert_eq!(rep.residual_after, rep.residual_before);
}
#[test]
fn rows_of_zero_scale() {
let a =
CsrMatrix::from_raw_parts(3, vec![0, 0, 1, 2], vec![1, 2], vec![1e-200, 2.0]).unwrap();
let b = [0.0, 0.0, 2.0];
let x = [Dd::ZERO, Dd::from_f64(1e-200), Dd::ONE];
let r = residual_dd(&a, &x, &b).unwrap();
assert_eq!(r, vec![Dd::ZERO; 3]);
assert!(rows_converged(&a, &x, &b, &r, 2f64.powi(-90)));
let mut y = x;
let rep = polish(
&a,
&b,
&mut y,
&mut |_| panic!("no solve"),
&PolishOptions::default(),
)
.unwrap();
assert_eq!((rep.stop, rep.iterations), (PolishStop::Converged, 0));
let fake = [Dd::from_f64(1e-300), Dd::ZERO, Dd::ZERO];
assert!(!rows_converged(&a, &x, &b, &fake, 1e300));
let fake = [Dd::ZERO, Dd::ZERO, Dd::NAN];
assert!(!rows_converged(&a, &x, &b, &fake, 1e300));
let big =
CsrMatrix::from_raw_parts(2, vec![0, 2], vec![0, 1], vec![1e150, -1e150]).unwrap();
let xb = [Dd::from_f64(1.5e158), Dd::from_f64(1.5e158)];
let rb = residual_dd(&big, &xb, &[0.0]).unwrap();
assert_eq!(rb, vec![Dd::ZERO]);
assert!(!rows_converged(&big, &xb, &[0.0], &rb, 2f64.powi(-90)));
let rb = [Dd::from_f64(1e290)];
assert!(!rows_converged(&big, &xb, &[0.0], &rb, 2f64.powi(-90)));
}
#[test]
fn defaults_are_those_of_the_contract() {
let o = PolishOptions::default();
assert_eq!(
(o.tol, o.min_progress, o.max_iter),
(2f64.powi(-90), 0.5, 10)
);
}
fn solve_small(damping: f64) -> impl FnMut(&mut [f64]) {
move |s: &mut [f64]| {
let (p, q) = (s[0], s[1]);
s[0] = damping * (3.0 * p - q) / 5.0;
s[1] = damping * (2.0 * q - p) / 5.0;
}
}
#[test]
fn polish_converges_and_reports() {
let a = small();
let b = [1.0, 1.0]; let mut x = [Dd::from_f64(0.4), Dd::from_f64(0.2)];
let rep = polish(
&a,
&b,
&mut x,
&mut solve_small(1.0),
&PolishOptions::default(),
)
.unwrap();
assert_eq!(rep.stop, PolishStop::Converged);
assert!(rep.iterations >= 1 && rep.iterations <= 3, "{rep:?}");
assert!(
rep.residual_before > 1e-17 && rep.residual_after < 1e-30,
"{rep:?}"
);
assert!(x[0].lo() != 0.0 && x[1].lo() != 0.0);
let cert = norm_inf_bound(&residual_of_dd(&a, &x, &b).unwrap());
assert!(cert < 1e-30, "{cert:e}");
let mut x = [Dd::ONE, Dd::from_f64(2.0)];
let rep = polish(
&a,
&[4.0, 7.0],
&mut x,
&mut |_| panic!("no solve"),
&PolishOptions::default(),
)
.unwrap();
assert_eq!((rep.stop, rep.iterations), (PolishStop::Converged, 0));
assert_eq!((rep.residual_before, rep.residual_after), (0.0, 0.0));
let empty = CsrMatrix::from_raw_parts(0, vec![0], vec![], vec![]).unwrap();
let rep = polish(&empty, &[], &mut [], &mut |_| {}, &PolishOptions::default()).unwrap();
assert_eq!((rep.stop, rep.iterations), (PolishStop::Converged, 0));
}
#[test]
fn polish_stops_for_each_reason() {
let a = small();
let b = [1.0, 1.0];
let start = [Dd::from_f64(0.5), Dd::from_f64(0.5)];
let o = PolishOptions::default();
let mut x = start;
let rep = polish(&a, &b, &mut x, &mut |_| {}, &o).unwrap();
assert_eq!((rep.stop, rep.iterations), (PolishStop::Stagnated, 0));
assert_eq!(x, start);
assert_eq!(rep.residual_after, rep.residual_before);
assert_eq!(rep.residual_before, 1.0);
let mut x = start;
let rep = polish(&a, &b, &mut x, &mut solve_small(0.4), &o).unwrap();
assert_eq!((rep.stop, rep.iterations), (PolishStop::Stagnated, 1));
assert!(rep.residual_after < rep.residual_before && x != start);
let slow = PolishOptions {
min_progress: 0.9,
..o
};
let mut x = start;
let rep = polish(&a, &b, &mut x, &mut solve_small(0.4), &slow).unwrap();
assert_eq!((rep.stop, rep.iterations), (PolishStop::IterationLimit, 10));
assert!(rep.residual_after < 0.01 * rep.residual_before, "{rep:?}");
let none = PolishOptions { max_iter: 0, ..o };
let mut x = start;
let rep = polish(&a, &b, &mut x, &mut |_| panic!("no solve"), &none).unwrap();
assert_eq!((rep.stop, rep.iterations), (PolishStop::IterationLimit, 0));
assert_eq!(x, start);
let mut x = start;
let rep = polish(&a, &b, &mut x, &mut |s| s[0] = f64::NAN, &o).unwrap();
assert_eq!((rep.stop, rep.iterations), (PolishStop::NotFinite, 0));
assert_eq!(x, start);
let mut x = [Dd::NAN, Dd::ONE];
let rep = polish(&a, &b, &mut x, &mut |_| panic!("no solve"), &o).unwrap();
assert_eq!((rep.stop, rep.iterations), (PolishStop::NotFinite, 0));
assert!(rep.residual_before.is_nan() && rep.residual_after.is_nan());
let mut x = start;
let rep = polish(&a, &b, &mut x, &mut |s| s[0] = 1e308, &o).unwrap();
assert_eq!((rep.stop, rep.iterations), (PolishStop::NotFinite, 0));
assert_eq!(x, start);
assert_eq!(rep.residual_after, rep.residual_before);
}
}