use multisolver::gcr::{newton_refined, GcrOpts};
use multisolver::multidouble::linalg::ld_for;
use multisolver::newton::{exact, newton, newton_chord, NewtonOpts, NewtonReport};
use multisolver::prec::{max_abs, nan_max, parts};
use multisolver::{Double, Jvp, Native, Precision, Problem, Quad, DD};
use std::cell::Cell;
const N: usize = 12;
struct Cubic<P: Precision<Native>> {
c: P::Scalar,
b: Vec<P::Scalar>,
diag_err: f64,
jvp_err: f64,
jacobians: Cell<usize>,
}
impl<P: Precision<Native>> Cubic<P> {
fn new(diag_err: f64) -> (Self, Vec<Vec<f64>>) {
let c = P::from_dd(DD::from_f64(0.3));
let zs: Vec<P::Scalar> = (0..N)
.map(|i| P::from_dd(DD::from_f64(0.5 + 0.1 * (i as f64).sin())))
.collect();
let mut pr = Cubic {
c,
b: vec![P::ZERO; N],
diag_err,
jvp_err: 1.0,
jacobians: Cell::new(0),
};
pr.b = pr.terms(&zs);
(pr, to_parts::<P>(&zs))
}
fn terms(&self, z: &[P::Scalar]) -> Vec<P::Scalar> {
(0..N)
.map(|i| z[i] * z[i] * z[i] + z[i] + self.c * z[(i + 1) % N])
.collect()
}
}
fn scalars<P: Precision<Native>>(z: &[&[f64]]) -> Vec<P::Scalar> {
(0..z[0].len())
.map(|i| P::from_raw(&z.iter().map(|p| p[i]).collect::<Vec<_>>()))
.collect()
}
fn to_parts<P: Precision<Native>>(v: &[P::Scalar]) -> Vec<Vec<f64>> {
(0..P::PARTS)
.map(|q| v.iter().map(|&x| P::part(x, q)).collect())
.collect()
}
impl<P: Precision<Native>> Problem<P> for Cubic<P> {
fn len(&self) -> usize {
N
}
fn residual(&self, z: &[&[f64]], _par: bool) -> Result<Vec<P::Scalar>, String> {
let z = scalars::<P>(z);
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> {
self.jacobians.set(self.jacobians.get() + 1);
let z = scalars::<P>(z);
let three = P::from_dd(DD::from_f64(3.0));
let err = P::from_dd(DD::from_f64(self.diag_err));
let ld = ld_for(N);
let mut c = vec![vec![0.0; ld * N]; P::PARTS];
for i in 0..N {
let d = (three * z[i] * z[i] + P::ONE) * err;
for (q, cq) in c.iter_mut().enumerate() {
cq[i * ld + i] = P::part(d, q);
cq[((i + 1) % N) * ld + i] = P::part(self.c, q);
}
}
Ok((c, ld))
}
}
impl<P: Precision<Native>> Jvp<P> for Cubic<P> {
fn jvp(&self, z: &[&[f64]], v: &[&[f64]], _par: bool) -> Result<Vec<P::Scalar>, String> {
let (z, v) = (scalars::<P>(z), scalars::<P>(v));
let three = P::from_dd(DD::from_f64(3.0));
let err = P::from_dd(DD::from_f64(self.jvp_err));
Ok((0..N)
.map(|i| (three * z[i] * z[i] + P::ONE) * err * v[i] + self.c * v[(i + 1) % N])
.collect())
}
}
fn run<P: Precision<Native>>(diag_err: f64, tol: f64) -> (bool, usize, f64, f64) {
let (pr, zs) = Cubic::<P>::new(diag_err);
let mut z = start(&zs);
let opts = NewtonOpts {
tol,
max_iter: 8,
..Default::default()
};
let rep = newton::<P, _>(&pr, &mut z, &opts).unwrap();
let (zn, zt) = (scalars::<P>(&parts(&z)), scalars::<P>(&parts(&zs)));
let err = zn
.iter()
.zip(&zt)
.map(|(&a, &b)| P::to_dd(a - b).hi.abs())
.fold(0.0, nan_max);
let f = max_abs::<P>(&pr.residual(&parts(&z), false).unwrap());
(rep.converged, rep.scale.len(), f, err)
}
#[test]
fn newton_converges_on_a_problem_that_is_not_shooting() {
let (ok, steps, f, err) = run::<Double>(1.0, 1e-28);
println!("double-double: converged {ok} in {steps} steps, max |F| {f:.3e}, max |z - z*| {err:.3e}");
assert_eq!(checks((ok, f, err), 1e-28, 1e-27), [true; 3]);
let (ok, steps, f, err) = run::<Quad>(1.0, 1e-60);
println!("quad-double: converged {ok} in {steps} steps, max |F| {f:.3e}, max |z - z*| {err:.3e}");
assert_eq!(checks((ok, f, err), 1e-60, 1e-59), [true; 3]);
}
fn checks((ok, f, err): (bool, f64, f64), ftol: f64, etol: f64) -> [bool; 3] {
[ok, f <= ftol, err <= etol]
}
#[test]
fn newton_control_wrong_jacobian_does_not_converge() {
let (ok, steps, f, err) = run::<Double>(1.1, 1e-28);
println!("control, diagonal 10% off: converged {ok} in {steps} steps, max |F| {f:.3e}, max |z - z*| {err:.3e}");
assert_eq!(checks((ok, f, err), 1e-28, 1e-27), [false; 3], "control did not fire");
let (ok, steps, f, err) = run::<Quad>(1.1, 1e-60);
println!("control, quad-double: converged {ok} in {steps} steps, max |F| {f:.3e}, max |z - z*| {err:.3e}");
assert_eq!(
checks((ok, f, err), 1e-60, 1e-59),
[false; 3],
"quad-double control did not fire"
);
}
fn start(zs: &[Vec<f64>]) -> Vec<Vec<f64>> {
let mut z = zs.to_vec();
for (i, v) in z[0].iter_mut().enumerate() {
*v += 1e-2 * (1.0 + 0.5 * (3.0 * i as f64).cos());
}
z
}
fn chord(every: usize, max_iter: usize) -> (NewtonReport, Vec<Vec<f64>>, usize) {
let (pr, zs) = Cubic::<Double>::new(1.0);
let mut z = start(&zs);
let opts = NewtonOpts {
tol: 1e-28,
max_iter,
..Default::default()
};
let rep = if every == 0 {
newton::<Double, _>(&pr, &mut z, &opts).unwrap()
} else {
newton_chord::<Double, _>(&pr, &mut z, &opts, every).unwrap()
};
(rep, z, pr.jacobians.get())
}
fn bits(rep: &NewtonReport, z: &[Vec<f64>]) -> Vec<u64> {
rep.fnorm
.iter()
.chain(&rep.scale)
.chain(&rep.theta)
.chain(z.iter().flatten())
.map(|v| v.to_bits())
.chain([rep.converged as u64])
.collect()
}
fn same_as_newton(every: usize) -> [bool; 2] {
let (ra, za, ja) = chord(0, 8);
let (rb, zb, jb) = chord(every, 8);
[bits(&ra, &za) == bits(&rb, &zb), ja == jb]
}
#[test]
fn chord_every_step_is_newton() {
assert_eq!(same_as_newton(1), [true; 2], "newton_chord(1) differs from newton");
assert_eq!(same_as_newton(3), [false; 2], "control did not fire");
}
fn reuses(rep: &NewtonReport, jac: usize, every: usize) -> bool {
let steps = rep.scale.len();
rep.converged && jac == steps.div_ceil(every) && jac < steps
}
#[test]
fn chord_reuses_the_factors() {
let (rep, _, jac) = chord(3, 12);
let steps = rep.scale.len();
println!(
"every 3: converged {} in {steps} steps, {jac} Jacobians, max |F| {:.3e}",
rep.converged,
rep.fnorm.last().unwrap()
);
assert!(reuses(&rep, jac, 3));
let (rep, _, jac) = chord(1, 12);
println!("control, every 1: {} steps, {jac} Jacobians", rep.scale.len());
assert_eq!(jac, rep.scale.len(), "control: every step forms its Jacobian");
assert!(!reuses(&rep, jac, 3), "control did not fire");
}
#[test]
fn chord_refuses_every_zero() {
let (pr, zs) = Cubic::<Double>::new(1.0);
let mut z = start(&zs);
assert!(newton_chord::<Double, _>(&pr, &mut z, &NewtonOpts::default(), 0).is_err());
}
fn refined(jvp_err: f64) -> (bool, usize, f64, usize) {
let (mut pr, zs) = Cubic::<Double>::new(1.1);
pr.jvp_err = jvp_err;
let mut z = start(&zs);
let opts = NewtonOpts {
tol: 1e-28,
max_iter: 8,
..Default::default()
};
let g = GcrOpts {
step_tol: 1e-10,
..Default::default()
};
let (rep, products) =
newton_refined::<Double, _, _>(&pr, &mut z, &opts, &g, |z| exact::<Double, _>(&pr, z, false)).unwrap();
(rep.converged, rep.scale.len(), *rep.fnorm.last().unwrap(), products)
}
#[test]
fn refined_newton_converges_on_a_wrong_preconditioner() {
let (ok, steps, f, products) = refined(1.0);
println!("refined: converged {ok} in {steps} steps, max |F| {f:.3e}, {products} products");
assert!(ok && f <= 1e-28);
}
#[test]
fn refined_newton_control_wrong_products_do_not_converge() {
let (ok, steps, f, _) = refined(1.1);
println!("control, products 10% off: converged {ok} in {steps} steps, max |F| {f:.3e}");
assert!(!ok, "control did not fire");
}