use multisolver::lm::{gram, levenberg_marquardt, levenberg_marquardt_with, LmOpts};
use multisolver::multidouble::linalg::ld_for;
use multisolver::newton::{lowered, newton, Lower, NewtonOpts};
use multisolver::prec::{max_abs, nan_max, parts};
use multisolver::{Double, Native, Octo, Precision, Problem, Quad, DD};
fn matrix(n: usize, bump: f64) -> (Vec<Vec<f64>>, usize, Vec<DD>) {
let ld = ld_for(n);
let mut c = vec![vec![1e300; ld * n]; 2];
for j in 0..n {
for i in 0..n {
let mut v = DD::new(((3 * i + 7 * j) as f64).sin(), 1e-17 * ((i + j) as f64).cos())
+ DD::from_f64((i * j) as f64 / (n * n) as f64);
if (i, j) == (2, 3) {
v = v * DD::new(1.0, bump);
}
(c[0][j * ld + i], c[1][j * ld + i]) = (v.hi, v.lo);
}
}
(c, ld, (0..n).map(|i| DD::from_f64((i as f64).cos())).collect())
}
#[derive(Clone, Copy, Debug)]
enum Fault {
None,
J,
B,
Nan,
}
fn gram_vs_scalar(fault: Fault) -> (f64, f64) {
let n = 21;
let (c, ld, b) = matrix(n, 0.0);
let (cb, _, _) = matrix(n, if matches!(fault, Fault::J) { 1e-20 } else { 0.0 });
let mut bb = b.clone();
match fault {
Fault::B => bb[3] = bb[3] * DD::new(1.0, 1e-20),
Fault::Nan => bb[0] = DD::from_f64(f64::NAN),
_ => {}
}
let (g, jb) = gram::<Double>(n, ld, &cb, &bb, true);
let col = |j: usize| -> Vec<DD> { (0..n).map(|i| DD::new(c[0][j * ld + i], c[1][j * ld + i])).collect() };
let dot = |x: &[DD], y: &[DD]| <Double as Precision<Native>>::dot(x.iter().copied().zip(y.iter().copied()));
let (mut eg, mut ej, mut scale) = (0.0f64, 0.0f64, 0.0f64);
for j in 0..n {
for i in 0..n {
let want = dot(&col(i), &col(j));
let got = DD::new(g[0][j * ld + i], g[1][j * ld + i]);
eg = nan_max(eg, (got - want).hi.abs());
scale = nan_max(scale, want.hi.abs());
}
ej = nan_max(ej, (jb[j] - dot(&col(j), &b)).hi.abs());
}
(eg / scale, ej / scale)
}
fn gram_checks((eg, ej): (f64, f64)) -> [bool; 2] {
[eg <= 1e-30, ej <= 1e-30]
}
#[test]
fn gram_matches_scalar_dot_products() {
let (eg, ej) = gram_vs_scalar(Fault::None);
println!("gram against scalar dots: G {eg:.3e}, g {ej:.3e}");
assert_eq!(gram_checks((eg, ej)), [true; 2]);
for (fault, want) in [
(Fault::J, [false; 2]),
(Fault::B, [true, false]),
(Fault::Nan, [true, false]),
] {
let (eg, ej) = gram_vs_scalar(fault);
println!("control, {fault:?}: G {eg:.3e}, g {ej:.3e}");
assert_eq!(gram_checks((eg, ej)), want, "control {fault:?} did not fire");
}
}
struct Circle;
fn sc<P: Precision<Native>>(z: &[&[f64]], i: usize) -> P::Scalar {
P::from_raw(&z.iter().map(|p| p[i]).collect::<Vec<_>>())
}
impl<P: Precision<Native>> Problem<P> for Circle {
fn len(&self) -> usize {
2
}
fn residual(&self, z: &[&[f64]], _par: bool) -> Result<Vec<P::Scalar>, String> {
let (a, b) = (sc::<P>(z, 0), sc::<P>(z, 1));
Ok(vec![a * a + b * b - P::ONE, a - b])
}
fn jacobian(&self, z: &[&[f64]], _par: bool) -> Result<(Vec<Vec<f64>>, usize), String> {
let (a, b) = (sc::<P>(z, 0), sc::<P>(z, 1));
let two = P::from_dd(DD::from_f64(2.0));
let ld = ld_for(2);
let mut c = vec![vec![0.0; ld * 2]; P::PARTS];
for (q, cq) in c.iter_mut().enumerate() {
cq[0] = P::part(two * a, q);
cq[1] = P::part(P::ONE, q);
cq[ld] = P::part(two * b, q);
cq[ld + 1] = P::part(-P::ONE, q);
}
Ok((c, ld))
}
}
fn singular_start<P: Precision<Native>>() -> Vec<Vec<f64>> {
(0..P::PARTS)
.map(|q| if q == 0 { vec![0.5, -0.5] } else { vec![0.0, 0.0] })
.collect()
}
fn circle<P: Precision<Native>>(tol: f64) -> (bool, usize, Vec<Vec<f64>>) {
let mut z = singular_start::<P>();
let opts = LmOpts {
tol,
..Default::default()
};
let rep = levenberg_marquardt::<P, _>(&Circle, &mut z, &opts).unwrap();
(rep.converged, rep.mu.len(), z)
}
fn circle_errors<P: Precision<Native>>(z: &[Vec<f64>]) -> (f64, f64, f64) {
let (a, b) = (sc::<P>(&parts(z), 0), sc::<P>(&parts(z), 1));
let f = max_abs::<P>(&Problem::<P>::residual(&Circle, &parts(z), false).unwrap());
let two = P::from_dd(DD::from_f64(2.0));
(f, P::to_dd(a - b).hi.abs(), P::to_dd(two * a * a - P::ONE).hi.abs())
}
fn circle_checks((f, d, r): (f64, f64, f64), tol: f64) -> [bool; 3] {
[f <= tol, d <= tol, r <= tol]
}
fn circle_case<P: Precision<Native>>(name: &str, tol: f64, eps: f64) {
let (ok, steps, z) = circle::<P>(tol);
let (f, d, r) = circle_errors::<P>(&z);
println!("{name}: converged {ok} after {steps} LM steps, max |F| {f:.3e}, |z0 - z1| {d:.3e}, |2 z0^2 - 1| {r:.3e}");
assert!(ok && circle_checks((f, d, r), tol) == [true; 3]);
let mut zw = z.clone();
let a = sc::<P>(&parts(&z), 0) + P::from_dd(DD::from_f64(eps));
for (q, p) in zw.iter_mut().enumerate() {
p[0] = P::part(a, q);
}
let (f, d, r) = circle_errors::<P>(&zw);
println!("control, z0 off by {eps:.0e}: max |F| {f:.3e}, |z0 - z1| {d:.3e}, |2 z0^2 - 1| {r:.3e}");
assert_eq!(circle_checks((f, d, r), tol), [false; 3], "control did not fire");
}
#[test]
fn lm_starts_where_the_jacobian_is_singular() {
circle_case::<Double>("double-double", 1e-28, 1e-20);
circle_case::<Quad>("quad-double", 1e-60, 1e-50);
let mut z = singular_start::<Double>();
let nr = newton::<Double, _>(&Circle, &mut z, &NewtonOpts::default());
println!(
"control, Newton from the same start: {:?}",
nr.as_ref().map(|r| r.converged)
);
assert!(nr.map_or(true, |r| !r.converged), "control did not fire");
}
struct Weak;
impl Problem<Double> for Weak {
fn len(&self) -> usize {
2
}
fn residual(&self, z: &[&[f64]], _par: bool) -> Result<Vec<DD>, String> {
Ok(vec![
DD::from_f64(1e-14) * (DD::new(z[0][0], z[1][0]) - DD::ONE),
DD::ZERO,
])
}
fn jacobian(&self, _z: &[&[f64]], _par: bool) -> Result<(Vec<Vec<f64>>, usize), String> {
let ld = ld_for(2);
let mut c = vec![vec![0.0; ld * 2]; 2];
c[0][0] = 1e-14;
Ok((c, ld))
}
}
#[test]
fn lm_goes_on_where_the_handover_fails() {
let check = |r: &Result<(bool, f64), String>| matches!(r, Ok((true, f)) if *f <= 1e-28);
let mut z = vec![vec![0.0; 2]; 2];
let lm = levenberg_marquardt::<Double, _>(&Weak, &mut z, &LmOpts::default());
let newton_report = lm.as_ref().map(|r| r.newton.is_some()).map_err(|e| e.clone());
let lm = lm.map(|r| {
(
r.converged,
max_abs::<Double>(&Weak.residual(&parts(&z), false).unwrap()),
)
});
println!("LM from (0, 0): {lm:?}, Newton report {newton_report:?}");
assert!(check(&lm) && newton_report == Ok(false));
let mut z = vec![vec![0.0; 2]; 2];
let nr =
newton::<Double, _>(&Weak, &mut z, &NewtonOpts::default()).map(|r| (r.converged, *r.fnorm.last().unwrap()));
println!("control, Newton from (0, 0): {nr:?}");
assert!(!check(&nr), "control did not fire");
}
struct Ident;
impl Problem<Quad> for Ident {
fn len(&self) -> usize {
1
}
fn residual(&self, z: &[&[f64]], _par: bool) -> Result<Vec<<Quad as Precision<Native>>::Scalar>, String> {
Ok(vec![sc::<Quad>(z, 0)])
}
fn jacobian(&self, _z: &[&[f64]], _par: bool) -> Result<(Vec<Vec<f64>>, usize), String> {
let ld = ld_for(1);
let mut c = vec![vec![0.0; ld]; 4];
c[0][0] = 1.0;
Ok((c, ld))
}
}
#[test]
fn lm_hands_over_with_its_own_tolerance() {
let check = |converged: bool, reported: f64, f: f64| converged && f <= 1e-60 && reported == f;
let start = || vec![vec![1e-30], vec![0.0], vec![0.0], vec![0.0]];
let fmax = |z: &[Vec<f64>]| max_abs::<Quad>(&Ident.residual(&parts(z), false).unwrap());
let mut z = start();
let opts = LmOpts {
tol: 1e-60,
..Default::default()
};
let rep = levenberg_marquardt::<Quad, _>(&Ident, &mut z, &opts).unwrap();
let last = *rep.fnorm.last().unwrap();
println!(
"LM to 1e-60: converged {}, max |F| {:.3e}, reported {last:.3e}, handed over {}",
rep.converged,
fmax(&z),
rep.newton.is_some()
);
assert!(check(rep.converged, last, fmax(&z)) && rep.newton.is_some());
let before = rep.fnorm[rep.fnorm.len() - 2];
println!("control, report without Newton's final entry: reported {before:.3e}");
assert!(!check(rep.converged, before, fmax(&z)), "control did not fire");
let mut z = start();
let nr = newton::<Quad, _>(&Ident, &mut z, &NewtonOpts::default()).unwrap();
println!(
"control, Newton at its own tolerance: converged {}, max |F| {:.3e}",
nr.converged,
fmax(&z)
);
assert!(
!check(nr.converged, *nr.fnorm.last().unwrap(), fmax(&z)),
"control did not fire"
);
}
struct Fragile {
limit: f64,
}
impl Problem<Double> for Fragile {
fn len(&self) -> usize {
1
}
fn residual(&self, z: &[&[f64]], _par: bool) -> Result<Vec<DD>, String> {
let a = DD::new(z[0][0], z[1][0]);
if a.hi > self.limit {
return Err("integration failed".into());
}
Ok(vec![a - DD::ONE])
}
fn jacobian(&self, _z: &[&[f64]], _par: bool) -> Result<(Vec<Vec<f64>>, usize), String> {
let ld = ld_for(1);
let mut c = vec![vec![0.0; ld]; 2];
c[0][0] = 1.0;
Ok((c, ld))
}
}
#[test]
fn lm_returns_the_problems_error() {
let check = |r: &Result<bool, String>| matches!(r, Err(e) if e == "integration failed");
let run = |limit: f64| {
let mut z = vec![vec![0.0], vec![0.0]];
levenberg_marquardt::<Double, _>(&Fragile { limit }, &mut z, &LmOpts::default()).map(|r| r.converged)
};
let r = run(0.5);
println!("residual an error past 0.5: {r:?}");
assert!(check(&r));
let r = run(2.0);
println!("control, residual valid up to 2: {r:?}");
assert!(!check(&r), "control did not fire");
}
#[test]
fn lm_hands_over_to_newton_with_lowered_factors() {
fn case<P: Precision<Native>>(name: &str, tol: f64, eps: f64) {
let mut z = singular_start::<P>();
let opts = LmOpts {
tol,
..Default::default()
};
let rep = levenberg_marquardt_with::<P, _, _>(&Circle, &mut z, &opts, |z| {
lowered::<P, _>(&Circle, z, Lower::Double, false)
})
.unwrap();
let handed = rep.newton.as_ref().is_some_and(|r| r.converged);
let (f, d, r) = circle_errors::<P>(&z);
println!(
"{name}: converged {} after {} LM steps, Newton converged {handed}, max |F| {f:.3e}, |z0 - z1| {d:.3e}, \
|2 z0^2 - 1| {r:.3e}",
rep.converged,
rep.mu.len()
);
assert!(
rep.converged && handed && circle_checks((f, d, r), tol) == [true; 3],
"{name}"
);
let mut zw = z.clone();
let a = sc::<P>(&parts(&z), 0) + P::from_dd(DD::from_f64(eps));
for (q, p) in zw.iter_mut().enumerate() {
p[0] = P::part(a, q);
}
let e = circle_errors::<P>(&zw);
assert_eq!(circle_checks(e, tol), [false; 3], "{name}: control did not fire");
}
case::<Quad>("quad-double", 1e-60, 1e-50);
case::<Octo>("octo-double", 1e-120, 1e-110);
}
const NP: usize = 12;
struct Planted<P: Precision<Native>> {
a: Vec<Vec<P::Scalar>>,
b: Vec<P::Scalar>,
rounded: bool,
}
impl<P: Precision<Native>> Planted<P> {
fn new(rounded: bool) -> (Self, Vec<P::Scalar>) {
let s = |x: f64| P::from_dd(DD::from_f64(x));
let a: Vec<Vec<P::Scalar>> = (0..NP)
.map(|i| {
(0..NP)
.map(|j| {
let v = if i == j {
4.0
} else {
0.5 * ((3 * i + 5 * j) as f64).sin()
};
P::from_dd(DD::new(v, v * 1e-17)) + s(v * 1e-40)
})
.collect()
})
.collect();
let zs: Vec<P::Scalar> = (0..NP).map(|i| s(0.5 + 0.1 * (i as f64).sin())).collect();
let mut pr = Planted {
a,
b: vec![P::ZERO; NP],
rounded: false,
};
pr.b = pr.terms(&zs);
pr.rounded = rounded;
(pr, zs)
}
fn terms(&self, z: &[P::Scalar]) -> Vec<P::Scalar> {
let c = P::from_dd(DD::from_f64(0.1));
self.a
.iter()
.zip(z)
.map(|(row, &zi)| {
let az = P::dot(row.iter().zip(z).map(|(&a, &x)| {
let a = if self.rounded { P::from_dd(P::to_dd(a)) } else { a };
(a, x)
}));
az + c * zi * zi * zi
})
.collect()
}
}
impl<P: Precision<Native>> Problem<P> for Planted<P> {
fn len(&self) -> usize {
NP
}
fn residual(&self, z: &[&[f64]], _par: bool) -> Result<Vec<P::Scalar>, String> {
let z: Vec<P::Scalar> = (0..NP).map(|i| sc::<P>(z, i)).collect();
Ok(self.terms(&z).iter().zip(&self.b).map(|(&t, &b)| t - b).collect())
}
fn jacobian(&self, z: &[&[f64]], _par: bool) -> Result<(Vec<Vec<f64>>, usize), String> {
let ld = ld_for(NP);
let c3 = P::from_dd(DD::from_f64(0.3));
let mut c = vec![vec![0.0; ld * NP]; P::PARTS];
for (i, row) in self.a.iter().enumerate() {
let zi = sc::<P>(z, i);
for (j, &a) in row.iter().enumerate() {
let v = if i == j { a + c3 * zi * zi } else { a };
for (q, cq) in c.iter_mut().enumerate() {
cq[j * ld + i] = P::part(v, q);
}
}
}
Ok((c, ld))
}
}
fn lm_alone<P: Precision<Native>>(tol: f64, rounded: bool) -> (bool, usize, f64, f64) {
let (pr, zs) = Planted::<P>::new(rounded);
let mut z: Vec<Vec<f64>> = (0..P::PARTS)
.map(|q| vec![if q == 0 { 1.0 } else { 0.0 }; NP])
.collect();
let opts = LmOpts {
tol,
newton_after: 0.0,
par: false,
..Default::default()
};
let rep = levenberg_marquardt::<P, _>(&pr, &mut z, &opts).unwrap();
let (exact, _) = Planted::<P>::new(false);
let f = max_abs::<P>(&exact.residual(&parts(&z), false).unwrap());
let err = (0..NP)
.map(|i| P::to_dd(sc::<P>(&parts(&z), i) - zs[i]).hi.abs())
.fold(0.0, nan_max);
(rep.converged, rep.mu.len(), f, err)
}
#[test]
fn lm_alone_reaches_the_precision_from_double_double_steps() {
let checks = |(_, _, f, err): (bool, usize, f64, f64), tol: f64| [f <= tol, err <= 10.0 * tol];
let case = |name: &str, r: (bool, usize, f64, f64), tol: f64, want: [bool; 2]| {
println!(
"{name}: converged {} after {} LM steps, max |F| {:.3e}, max |z - z*| {:.3e}",
r.0, r.1, r.2, r.3
);
assert!(r.0 && r.1 <= 50, "{name}: LM did not converge");
assert_eq!(checks(r, tol), want, "{name}");
};
case("quad-double", lm_alone::<Quad>(1e-60, false), 1e-60, [true; 2]);
case("octo-double", lm_alone::<Octo>(1e-120, false), 1e-120, [true; 2]);
case(
"control, quad-double, residual rounded to double-double",
lm_alone::<Quad>(1e-60, true),
1e-60,
[false; 2],
);
}