use multisolver::arclength::{
continuation, locate_fold, start, tangent, ArcOpts, AtParam, Bordered, FoldOpts, Path, Point,
};
use multisolver::multidouble::linalg::ld_for;
use multisolver::newton::{exact, lowered, newton, Damping, Factored, Lower, NewtonOpts};
use multisolver::prec::{nan_max, parts};
use multisolver::{Double, Family, Native, Precision, Quad, DD};
const N: usize = 5;
fn s<P: Precision<Native>>(x: f64) -> P::Scalar {
P::from_dd(DD::from_f64(x))
}
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()
}
struct Fold<P: Precision<Native>> {
b: Vec<Vec<P::Scalar>>,
dp_err: f64,
}
impl<P: Precision<Native>> Fold<P> {
fn new() -> Self {
let b = (0..N)
.map(|i| {
(0..N)
.map(|j| {
s::<P>(if i == j {
2.0
} else {
0.3 * ((1 + 3 * i + 5 * j) as f64).sin()
})
})
.collect()
})
.collect();
Fold { b, dp_err: 0.0 }
}
fn g(&self, z: &[P::Scalar], p: P::Scalar) -> Vec<P::Scalar> {
let half = s::<P>(0.5);
(0..N)
.map(|i| {
if i == 0 {
z[0] * z[0] + p * p - P::ONE
} else {
z[i] - (z[i - 1] * z[i - 1] + p) * half
}
})
.collect()
}
fn mix(&self, v: &[P::Scalar]) -> Vec<P::Scalar> {
self.b
.iter()
.map(|row| P::dot(row.iter().copied().zip(v.iter().copied())))
.collect()
}
}
impl<P: Precision<Native>> Family<P> for Fold<P> {
fn len(&self) -> usize {
N
}
fn residual_at(&self, z: &[&[f64]], p: P::Scalar, _par: bool) -> Result<Vec<P::Scalar>, String> {
Ok(self.mix(&self.g(&scalars::<P>(z), p)))
}
fn jacobian_at(&self, z: &[&[f64]], _p: P::Scalar, _par: bool) -> Result<(Vec<Vec<f64>>, usize), String> {
let z = scalars::<P>(z);
let mut gz = vec![vec![P::ZERO; N]; N];
for j in 0..N {
gz[j][j] = if j == 0 { s::<P>(2.0) * z[0] } else { P::ONE };
if j + 1 < N {
gz[j][j + 1] = -z[j];
}
}
let ld = ld_for(N);
let mut c = vec![vec![0.0; ld * N]; P::PARTS];
for (j, col) in gz.iter().enumerate() {
for (i, &v) in self.mix(col).iter().enumerate() {
for (q, cq) in c.iter_mut().enumerate() {
cq[j * ld + i] = P::part(v, q);
}
}
}
Ok((c, ld))
}
fn dp_at(&self, _z: &[&[f64]], p: P::Scalar, _par: bool) -> Result<Vec<P::Scalar>, String> {
let gp: Vec<P::Scalar> = (0..N)
.map(|i| if i == 0 { s::<P>(2.0) * p } else { -s::<P>(0.5) })
.collect();
let mut fp = self.mix(&gp);
fp[0] = fp[0] * P::from_dd(DD::new(1.0, self.dp_err));
Ok(fp)
}
}
fn z_start<P: Precision<Native>>() -> Vec<Vec<f64>> {
let mut z = vec![P::ONE];
for i in 1..N {
z.push(z[i - 1] * z[i - 1] * s::<P>(0.5));
}
to_parts::<P>(&z)
}
fn ex<P: Precision<Native>>(
b: &Bordered<'_, P, Fold<P>>,
w: &[&[f64]],
) -> Result<multisolver::newton::Exact<P>, String> {
exact::<P, _>(b, w, false)
}
fn corrector(tol: f64) -> NewtonOpts {
NewtonOpts {
tol,
par: false,
..Default::default()
}
}
fn branch<P: Precision<Native>>(fam: &Fold<P>, tol: f64) -> Path<P> {
let z0 = z_start::<P>();
let a = start::<P, _, _>(fam, &parts(&z0), P::ZERO, 1.0, false, ex::<P>).unwrap();
let opts = ArcOpts {
max_points: 200,
newton: corrector(tol),
..Default::default()
};
continuation::<P, _, _>(fam, a, &opts, ex::<P>, |pt| pt.z[0][0] < -0.5).unwrap()
}
fn g_err<P: Precision<Native>>(fam: &Fold<P>, z: &[Vec<f64>], p: P::Scalar) -> f64 {
fam.g(&scalars::<P>(&parts(z)), p)
.iter()
.map(|&v| P::to_dd(v).hi.abs())
.fold(0.0, nan_max)
}
fn path_checks<P: Precision<Native>>(fam: &Fold<P>, path: &Path<P>, gtol: f64) -> [bool; 3] {
let z1 = |i: usize| path.points[i].z[0][0];
let last = path.points.len() - 1;
let fold_ok = path.folds.len() == 1 && z1(path.folds[0]) > 0.0 && z1(path.folds[0] + 1) < 0.0;
let on = path
.points
.iter()
.map(|pt| g_err::<P>(fam, &pt.z, pt.p))
.fold(0.0, nan_max);
[z1(last) < -0.5, fold_ok, on <= gtol]
}
#[test]
fn continuation_passes_a_fold() {
let fam = Fold::<Double>::new();
let path = branch::<Double>(&fam, 1e-30);
let last = &path.points[path.points.len() - 1];
println!(
"double-double: {} points, {} refused, folds after {:?}, last (z_1, p) = ({:.6}, {:.6})",
path.points.len(),
path.refused,
path.folds,
last.z[0][0],
last.p.hi
);
assert_eq!(path_checks(&fam, &path, 1e-27), [true; 3]);
let famq = Fold::<Quad>::new();
let pq = branch::<Quad>(&famq, 1e-62);
println!("quad-double: {} points, folds after {:?}", pq.points.len(), pq.folds);
assert_eq!(path_checks(&famq, &pq, 1e-59), [true; 3]);
let mut z = z_start::<Double>();
let mut reached = f64::INFINITY;
let mut stopped_at = None;
for k in 1..=15 {
let p = 0.1 * k as f64;
let pr = AtParam {
fam: &fam,
p: DD::from_f64(p),
};
let mut zt = z.clone();
let ok = newton::<Double, _>(&pr, &mut zt, &corrector(1e-30)).is_ok_and(|r| r.converged);
if !ok {
stopped_at = Some(p);
break;
}
z = zt;
reached = z[0][0];
}
println!("control, continuation in p: stopped at p = {stopped_at:?}, last z_1 {reached:.6}");
assert!(
stopped_at.is_some_and(|p| p <= 1.1 + 1e-12) && reached >= -0.5,
"control did not fire"
);
let mut cut = path.clone();
cut.points.truncate(path.folds[0] + 1);
cut.folds.clear();
assert_eq!(
path_checks(&fam, &cut, 1e-27),
[false, false, true],
"control, cut path"
);
let mut moved = path.clone();
let i = moved.points.len() / 2;
let z3 = DD::new(moved.points[i].z[0][2], moved.points[i].z[1][2]) + DD::from_f64(1e-20);
(moved.points[i].z[0][2], moved.points[i].z[1][2]) = (z3.hi, z3.lo);
assert_eq!(
path_checks(&fam, &moved, 1e-27),
[true, true, false],
"control, moved point"
);
}
fn fold_checks<P: Precision<Native>>(z: &[Vec<f64>], p: P::Scalar, ptol: f64, ztol: f64) -> [bool; 3] {
let zs = scalars::<P>(&parts(z));
let want = [0.5, 0.625, 0.6953125, 0.741729736328125];
let rest = (1..N)
.map(|i| P::to_dd(zs[i] - s::<P>(want[i - 1])).hi.abs())
.fold(0.0, nan_max);
[
P::to_dd(p - P::ONE).hi.abs() <= ptol,
P::to_dd(zs[0]).hi.abs() <= ztol,
rest <= ptol,
]
}
fn located<P: Precision<Native>>(tol: f64, tp_tol: f64) -> (Point<P>, usize, Point<P>) {
let fam = Fold::<P>::new();
let path = branch::<P>(&fam, tol);
let i = path.folds[0];
let opts = FoldOpts {
tol: tp_tol,
..Default::default()
};
let (pt, it) = locate_fold::<P, _, _>(&fam, &path.points[i], path.ds[i], &opts, &corrector(tol), ex::<P>).unwrap();
(pt, it, path.points[i].clone())
}
#[test]
fn fold_is_located_to_the_precision() {
let (pt, it, a) = located::<Double>(1e-30, 1e-15);
let (z, p, za, pa) = (pt.z, pt.p, a.z, a.p);
println!(
"double-double: {it} corrections, p - 1 = {:.3e}, z_1 = {:.3e}",
(p - DD::ONE).hi,
z[0][0]
);
assert_eq!(fold_checks::<Double>(&z, p, 1e-29, 1e-14), [true; 3]);
let fa = fold_checks::<Double>(&za, pa, 1e-29, 1e-14);
println!(
"control, the bracket's first point: p = {:.6}, z_1 = {:.6}",
pa.hi, za[0][0]
);
assert!(!fa[0] && !fa[1], "control did not fire");
let (ptq, itq, _) = located::<Quad>(1e-62, 1e-31);
let (zq, pq) = (ptq.z, ptq.p);
let dq = <Quad as Precision<Native>>::to_dd(pq - <Quad as Precision<Native>>::ONE).hi;
println!(
"quad-double: {itq} corrections, p - 1 = {dq:.3e}, z_1 = {:.3e}",
zq[0][0]
);
assert_eq!(fold_checks::<Quad>(&zq, pq, 1e-61, 1e-30), [true; 3]);
}
fn tangent_errors<P: Precision<Native>>(fam: &Fold<P>, dir: f64) -> (f64, f64, f64) {
let z0 = z_start::<P>();
let n1 = N + 1;
let mut d = vec![P::ZERO; n1];
d[N] = s::<P>(dir);
let t = tangent::<P, _, _>(fam, &parts(&z0), P::ZERO, &d, false, ex::<P>).unwrap();
errors_of::<P>(&t)
}
fn errors_of<P: Precision<Native>>(t: &[P::Scalar]) -> (f64, f64, f64) {
let z0 = z_start::<P>();
let zs = scalars::<P>(&parts(&z0));
let mut dz = vec![P::ZERO];
for i in 1..N {
dz.push((s::<P>(2.0) * zs[i - 1] * dz[i - 1] + P::ONE) * s::<P>(0.5));
}
let inv = P::from_dd(DD::ONE / P::to_dd(t[N]));
let inv = inv + inv * (P::ONE - t[N] * inv);
let inv = inv + inv * (P::ONE - t[N] * inv);
let err = (0..N).map(|i| P::to_dd(t[i] * inv - dz[i]).hi.abs()).fold(0.0, nan_max);
let norm = t.iter().map(|&v| P::to_dd(v).hi.powi(2)).sum::<f64>().sqrt();
(err, P::to_dd(t[N]).hi, norm - 1.0)
}
#[test]
fn tangent_is_the_branch_direction() {
let fam = Fold::<Double>::new();
let (e, tp, dn) = tangent_errors::<Double>(&fam, 1.0);
println!("double-double: t_z / t_p off by {e:.3e}, t_p {tp:.6}, |t| - 1 = {dn:.3e}");
assert!(e <= 1e-30 && tp > 0.0 && dn.abs() <= 1e-15);
let (_, tm, _) = tangent_errors::<Double>(&fam, -1.0);
assert!(tm < 0.0, "oriented by -1: t_p {tm}");
let (eq, tq, dq) = tangent_errors::<Quad>(&Fold::<Quad>::new(), 1.0);
println!("quad-double: t_z / t_p off by {eq:.3e}, t_p {tq:.6}, |t| - 1 = {dq:.3e}");
assert!(eq <= 1e-62 && tq > 0.0 && dq.abs() <= 1e-15);
let bad = Fold::<Double> {
dp_err: 1e-20,
..Fold::<Double>::new()
};
let (eb, _, _) = tangent_errors::<Double>(&bad, 1.0);
println!("control, dF/dp off by 1e-20: t_z / t_p off by {eb:.3e}");
assert!(eb > 1e-30, "control did not fire");
}
fn w_start<P: Precision<Native>>() -> Vec<Vec<f64>> {
z_start::<P>()
.into_iter()
.map(|q| q.into_iter().chain([0.0]).collect())
.collect()
}
fn tangent_f64<P: Precision<Native>>(fam: &Fold<P>) -> Vec<P::Scalar> {
let mut d = vec![P::ZERO; N + 1];
d[N] = P::ONE;
let f64_factors = |b: &Bordered<'_, P, Fold<P>>, w: &[&[f64]]| lowered::<P, _>(b, w, Lower::F64, false);
tangent::<P, _, _>(fam, &parts(&z_start::<P>()), P::ZERO, &d, false, f64_factors).unwrap()
}
#[test]
fn tangent_from_f64_factors_is_exact_to_the_precision() {
let fam = Fold::<Double>::new();
let (e, tp, dn) = errors_of::<Double>(&tangent_f64::<Double>(&fam));
println!("double-double, f64 factors: t_z / t_p off by {e:.3e}, t_p {tp:.6}, |t| - 1 = {dn:.3e}");
assert!(e <= 1e-30 && tp > 0.0 && dn.abs() <= 1e-15);
let famq = Fold::<Quad>::new();
let (eq, tq, dq) = errors_of::<Quad>(&tangent_f64::<Quad>(&famq));
println!("quad-double, f64 factors: t_z / t_p off by {eq:.3e}, t_p {tq:.6}, |t| - 1 = {dq:.3e}");
assert!(eq <= 1e-62 && tq > 0.0 && dq.abs() <= 1e-15);
let mut d = vec![DD::ZERO; N + 1];
d[N] = DD::ONE;
let b = Bordered {
fam: &fam,
t: d,
pred: vec![DD::ZERO; N + 1],
};
let lu = lowered::<Double, _>(&b, &parts(&w_start::<Double>()), Lower::F64, false).unwrap();
let mut e1 = vec![DD::ZERO; N + 1];
e1[N] = -DD::ONE;
let t1 = Factored::<Double>::solve_neg(&lu, &e1);
let (ec, _, _) = errors_of::<Double>(&t1);
println!("control, one solve with f64 factors: t_z / t_p off by {ec:.3e}");
assert!(ec > 1e-30, "control did not fire");
}
struct Pinch;
impl<P: Precision<Native>> Family<P> for Pinch {
fn len(&self) -> usize {
2
}
fn residual_at(&self, z: &[&[f64]], p: P::Scalar, _par: bool) -> Result<Vec<P::Scalar>, String> {
let z = scalars::<P>(z);
let u = z[0] + z[1];
Ok(vec![u, u + z[0] * z[0] + p])
}
fn jacobian_at(&self, z: &[&[f64]], _p: P::Scalar, _par: bool) -> Result<(Vec<Vec<f64>>, usize), String> {
let z = scalars::<P>(z);
let ld = ld_for(2);
let mut c = vec![vec![0.0; ld * 2]; P::PARTS];
let d = P::ONE + s::<P>(2.0) * z[0];
for (q, cq) in c.iter_mut().enumerate() {
let one = if q == 0 { 1.0 } else { 0.0 };
(cq[0], cq[1], cq[ld], cq[ld + 1]) = (one, P::part(d, q), one, one);
}
Ok((c, ld))
}
fn dp_at(&self, _z: &[&[f64]], _p: P::Scalar, _par: bool) -> Result<Vec<P::Scalar>, String> {
Ok(vec![P::ZERO, P::ONE])
}
}
fn pinch_fold<P: Precision<Native>>(tol: f64) -> (P::Scalar, P::Scalar, P::Scalar) {
let ex = |b: &Bordered<'_, P, Pinch>, w: &[&[f64]]| exact::<P, _>(b, w, false);
let f64_factors = |b: &Bordered<'_, P, Pinch>, w: &[&[f64]]| lowered::<P, _>(b, w, Lower::F64, false);
let z0 = to_parts::<P>(&[P::ONE, -P::ONE]);
let a = start::<P, _, _>(&Pinch, &parts(&z0), -P::ONE, 1.0, false, ex).unwrap();
let opts = ArcOpts {
max_points: 200,
newton: corrector(tol),
..Default::default()
};
let path = continuation::<P, _, _>(&Pinch, a, &opts, ex, |pt| pt.z[0][0] < -0.5).unwrap();
let i = path.folds[0];
let fopts = FoldOpts {
tol,
..Default::default()
};
let (pt, _) = locate_fold::<P, _, _>(
&Pinch,
&path.points[i],
path.ds[i],
&fopts,
&corrector(tol),
f64_factors,
)
.unwrap();
let z = scalars::<P>(&parts(&pt.z));
(z[0], z[0] + z[1], pt.p)
}
#[test]
fn fold_is_located_with_f64_factors() {
let check = |v: [f64; 3], tol: f64| v.map(|x| x.abs() <= tol);
let (z1, u, p) = pinch_fold::<Double>(1e-30);
let v = [z1.hi, u.hi, p.hi];
println!(
"double-double: z_1 {:.3e}, z_1 + z_2 {:.3e}, p {:.3e}",
v[0], v[1], v[2]
);
assert_eq!(check(v, 1e-29), [true; 3]);
let (z1, u, p) = pinch_fold::<Quad>(1e-62);
let hi = |x| <Quad as Precision<Native>>::to_dd(x).hi;
let vq = [hi(z1), hi(u), hi(p)];
println!(
"quad-double: z_1 {:.3e}, z_1 + z_2 {:.3e}, p {:.3e}",
vq[0], vq[1], vq[2]
);
assert_eq!(check(vq, 1e-61), [true; 3]);
assert!(!check([1e-17, 0.0, 0.0], 1e-29)[0], "control did not fire");
}
struct Bend {
fail_above: f64,
}
impl Family<Double> for Bend {
fn len(&self) -> usize {
1
}
fn residual_at(&self, z: &[&[f64]], p: DD, _par: bool) -> Result<Vec<DD>, String> {
if p.hi > self.fail_above {
return Err(format!("Bend: no residual at p = {}", p.hi));
}
let z = DD::new(z[0][0], z[1][0]);
Ok(vec![(DD::ONE - p) * z - p * p])
}
fn jacobian_at(&self, _z: &[&[f64]], p: DD, _par: bool) -> Result<(Vec<Vec<f64>>, usize), String> {
let ld = ld_for(1);
let d = DD::ONE - p;
let mut c = vec![vec![0.0; ld]; 2];
(c[0][0], c[1][0]) = (d.hi, d.lo);
Ok((c, ld))
}
fn dp_at(&self, z: &[&[f64]], p: DD, _par: bool) -> Result<Vec<DD>, String> {
Ok(vec![-DD::new(z[0][0], z[1][0]) - p.mul_f(2.0)])
}
}
fn bend_err(z: &[Vec<f64>], p: DD) -> f64 {
let z = DD::new(z[0][0], z[1][0]);
((DD::ONE - p) * z - p * p).hi.abs()
}
fn bend(fam: &Bend, max_points: usize) -> Result<Path<Double>, String> {
let ex = |b: &Bordered<'_, Double, Bend>, w: &[&[f64]]| exact::<Double, _>(b, w, false);
let a = start::<Double, _, _>(fam, &[&[0.0][..], &[0.0][..]], DD::ZERO, 1.0, false, ex)?;
let opts = ArcOpts {
ds: 1.0,
max_points,
newton: corrector(1e-30),
..Default::default()
};
continuation::<Double, _, _>(fam, a, &opts, ex, |_| false)
}
#[test]
fn continuation_refuses_a_singular_prediction() {
let path = bend(
&Bend {
fail_above: f64::INFINITY,
},
4,
)
.unwrap();
let second = &path.points[1];
let (z1, p1) = (DD::new(second.z[0][0], second.z[1][0]), second.p);
let worst = path.points.iter().map(|pt| bend_err(&pt.z, pt.p)).fold(0.0, nan_max);
println!(
"{} points, {} refused, second (z, p) = ({:.3e}, {:.3e}) off (1/2, 1/2), max |F| {worst:.3e}",
path.points.len(),
path.refused,
(z1 - DD::from_f64(0.5)).hi,
(p1 - DD::from_f64(0.5)).hi
);
assert!(path.points.len() == 4 && path.refused >= 1 && worst <= 1e-30);
assert!((z1 - DD::from_f64(0.5)).hi.abs() <= 1e-30 && (p1 - DD::from_f64(0.5)).hi.abs() <= 1e-30);
let mut z = second.z.clone();
let zm = DD::new(z[0][0], z[1][0]) + DD::from_f64(1e-20);
(z[0][0], z[1][0]) = (zm.hi, zm.lo);
assert!(bend_err(&z, p1) > 1e-30, "control, moved point");
let e = bend(&Bend { fail_above: 0.25 }, 4).unwrap_err();
println!("control, a failing residual: {e}");
assert!(e.starts_with("Bend: no residual"), "control, the problem's error");
}
fn fold_path(
ds: f64,
ds_min: f64,
theta_target: f64,
max_points: usize,
damping: Damping,
) -> Result<Path<Double>, String> {
let fam = Fold::<Double>::new();
let z0 = z_start::<Double>();
let a = start::<Double, _, _>(&fam, &parts(&z0), DD::ZERO, 1.0, false, ex::<Double>)?;
let opts = ArcOpts {
ds,
ds_min,
theta_target,
max_points,
newton: NewtonOpts {
damping,
..corrector(1e-30)
},
..Default::default()
};
continuation::<Double, _, _>(&fam, a, &opts, ex::<Double>, |_| false)
}
#[test]
fn continuation_keeps_steps_at_least_ds_min() {
let check = |path: &Path<Double>| path.points.len() == 6 && path.ds.iter().all(|&d| d >= 0.05);
let path = fold_path(0.05, 0.05, 1e-12, 6, Damping::Correction).unwrap();
println!("ds_min 0.05: steps {:?}", path.ds);
assert!(check(&path));
let c = fold_path(0.05, 0.025, 1e-12, 6, Damping::Correction).unwrap();
println!("control, ds_min 0.025: steps {:?}", c.ds);
assert!(!check(&c), "control did not fire");
}
#[test]
fn continuation_refuses_the_residual_rule() {
let e = fold_path(0.1, 1e-8, 0.125, 4, Damping::Residual);
println!("residual rule: {:?}", e.as_ref().map(|p| p.points.len()));
assert!(e.is_err());
assert!(
fold_path(0.1, 1e-8, 0.125, 4, Damping::Correction).is_ok(),
"control did not fire"
);
}
#[test]
fn continuation_stops_at_a_start_that_meets_stop() {
let fam = Fold::<Double>::new();
let z0 = z_start::<Double>();
let a = start::<Double, _, _>(&fam, &parts(&z0), DD::ZERO, 1.0, false, ex::<Double>).unwrap();
let opts = ArcOpts {
max_points: 2,
newton: corrector(1e-30),
..Default::default()
};
let path = continuation::<Double, _, _>(&fam, a.clone(), &opts, ex::<Double>, |_| true).unwrap();
println!(
"stop at the start: {} points, {} steps",
path.points.len(),
path.ds.len()
);
assert!(path.points.len() == 1 && path.ds.is_empty());
let c = continuation::<Double, _, _>(&fam, a, &opts, ex::<Double>, |_| false).unwrap();
assert!(!(c.points.len() == 1 && c.ds.is_empty()), "control did not fire");
}