use crate::prec::{max_abs, parts};
use crate::Problem;
use multidouble::dd::DD;
use multidouble::precision::Precision;
use multidouble::simd::Native;
use std::cell::RefCell;
use std::rc::Rc;
use std::time::Instant;
pub struct Step<P: Precision<Native>> {
pub dz: Vec<Vec<f64>>,
pub f: Vec<P::Scalar>,
pub lu: P::Lu,
pub t: [f64; 4],
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Damping {
Correction,
Residual,
}
#[derive(Clone, Copy, Debug)]
pub struct NewtonOpts {
pub tol: f64,
pub tol_dz: f64,
pub max_iter: usize,
pub max_halvings: usize,
pub lambda0: f64,
pub damping: Damping,
pub par: bool,
}
impl Default for NewtonOpts {
fn default() -> Self {
NewtonOpts {
tol: 1e-28,
tol_dz: 0.0,
max_iter: 20,
max_halvings: 10,
lambda0: 1.0,
damping: Damping::Correction,
par: true,
}
}
}
#[derive(Clone, Debug)]
pub struct NewtonReport {
pub fnorm: Vec<f64>,
pub scale: Vec<f64>,
pub theta: Vec<f64>,
pub dz_bar: Vec<f64>,
pub converged: bool,
}
impl NewtonReport {
pub fn error_estimate(&self) -> Option<f64> {
self.dz_bar.last().copied()
}
fn new() -> Self {
NewtonReport {
fnorm: Vec::new(),
scale: Vec::new(),
theta: Vec::new(),
dz_bar: Vec::new(),
converged: false,
}
}
}
fn axpy<P: Precision<Native>>(z: &[&[f64]], dz: &[P::Scalar], s: f64) -> Vec<Vec<f64>> {
let l = z[0].len();
let mut out: Vec<Vec<f64>> = (0..P::PARTS).map(|_| vec![0.0; l]).collect();
let sc = P::from_dd(DD::from_f64(s));
let mut a = vec![0.0; P::PARTS];
for i in 0..l {
for q in 0..P::PARTS {
a[q] = z[q][i];
}
let v = P::from_raw(&a) + sc * dz[i];
for (q, o) in out.iter_mut().enumerate() {
o[i] = P::part(v, q);
}
}
out
}
pub(crate) fn norm2<P: Precision<Native>>(v: &[P::Scalar]) -> f64 {
let m = max_abs::<P>(v);
if m == 0.0 || !m.is_finite() {
return m;
}
m * v.iter().map(|&x| P::to_dd(x).hi / m).map(|x| x * x).sum::<f64>().sqrt()
}
fn solve_neg<P: Precision<Native>>(lu: &P::Lu, r: &[P::Scalar]) -> Vec<P::Scalar> {
let mut b: Vec<P::Scalar> = r.iter().map(|&v| -v).collect();
P::lu_solve(lu, &mut b);
b
}
pub trait Factored<P: Precision<Native>> {
fn solve_neg(&self, r: &[P::Scalar]) -> Vec<P::Scalar>;
fn try_solve_neg(&self, r: &[P::Scalar]) -> Result<Vec<P::Scalar>, String> {
Ok(self.solve_neg(r))
}
}
impl<P: Precision<Native>, F: Factored<P>> Factored<P> for Rc<F> {
fn solve_neg(&self, r: &[P::Scalar]) -> Vec<P::Scalar> {
(**self).solve_neg(r)
}
fn try_solve_neg(&self, r: &[P::Scalar]) -> Result<Vec<P::Scalar>, String> {
(**self).try_solve_neg(r)
}
}
pub struct Exact<P: Precision<Native>>(pub P::Lu);
impl<P: Precision<Native>> Factored<P> for Exact<P> {
fn solve_neg(&self, r: &[P::Scalar]) -> Vec<P::Scalar> {
solve_neg::<P>(&self.0, r)
}
}
pub fn exact<P: Precision<Native>, Pr: Problem<P> + ?Sized>(
pr: &Pr,
z: &[&[f64]],
par: bool,
) -> Result<Exact<P>, String> {
let (c, ld) = pr.jacobian(z, par)?;
Ok(Exact(P::lu_factor(pr.len(), ld, c, par)?))
}
pub fn reuse<F>(
every: usize,
factor: impl Fn(&[&[f64]]) -> Result<F, String>,
) -> impl Fn(&[&[f64]]) -> Result<Rc<F>, String> {
assert!(every >= 1, "reuse: every must be at least 1");
let last: RefCell<Option<(usize, Rc<F>)>> = RefCell::new(None);
move |z| {
let mut last = last.borrow_mut();
if let Some((uses, f)) = last.as_mut() {
if *uses < every {
*uses += 1;
return Ok(f.clone());
}
}
let f = Rc::new(factor(z)?);
*last = Some((1, f.clone()));
Ok(f)
}
}
pub fn newton_step<P: Precision<Native>, Pr: Problem<P> + ?Sized>(
pr: &Pr,
z: &[&[f64]],
par: bool,
) -> Result<Step<P>, String> {
let l = pr.len();
let mut t = [0.0f64; 4];
let t0 = Instant::now();
let f = pr.residual(z, par)?;
t[0] = t0.elapsed().as_secs_f64();
let t0 = Instant::now();
let (c, ld) = pr.jacobian(z, par)?;
t[1] = t0.elapsed().as_secs_f64();
let t0 = Instant::now();
let lu = P::lu_factor(l, ld, c, par)?;
t[2] = t0.elapsed().as_secs_f64();
let t0 = Instant::now();
let b = solve_neg::<P>(&lu, &f);
t[3] = t0.elapsed().as_secs_f64();
let dz = (0..P::PARTS)
.map(|q| b.iter().map(|&v| P::part(v, q)).collect())
.collect();
Ok(Step { dz, f, lu, t })
}
pub fn newton<P: Precision<Native>, Pr: Problem<P> + ?Sized>(
pr: &Pr,
z: &mut Vec<Vec<f64>>,
opts: &NewtonOpts,
) -> Result<NewtonReport, String> {
newton_with::<P, Pr, _>(pr, z, opts, |z| exact::<P, Pr>(pr, z, opts.par))
}
pub fn newton_chord<P: Precision<Native>, Pr: Problem<P> + ?Sized>(
pr: &Pr,
z: &mut Vec<Vec<f64>>,
opts: &NewtonOpts,
every: usize,
) -> Result<NewtonReport, String> {
if every == 0 {
return Err("newton_chord: every must be at least 1".into());
}
newton_with::<P, Pr, _>(pr, z, opts, reuse(every, |z| exact::<P, Pr>(pr, z, opts.par)))
}
pub fn newton_with<P: Precision<Native>, Pr: Problem<P> + ?Sized, F: Factored<P>>(
pr: &Pr,
z: &mut Vec<Vec<f64>>,
opts: &NewtonOpts,
factor: impl Fn(&[&[f64]]) -> Result<F, String>,
) -> Result<NewtonReport, String> {
if !(opts.lambda0 > 0.0 && opts.lambda0 <= 1.0) {
return Err(format!("newton: lambda0 must lie in (0, 1], not {}", opts.lambda0));
}
if opts.max_halvings > 1074 {
return Err(format!(
"newton: max_halvings {} is beyond f64's range (at most 1074)",
opts.max_halvings
));
}
match opts.damping {
Damping::Correction => newton_correction::<P, Pr, F>(pr, z, opts, factor),
Damping::Residual => newton_residual::<P, Pr, F>(pr, z, opts, factor),
}
}
fn newton_correction<P: Precision<Native>, Pr: Problem<P> + ?Sized, F: Factored<P>>(
pr: &Pr,
z: &mut Vec<Vec<f64>>,
opts: &NewtonOpts,
factor: impl Fn(&[&[f64]]) -> Result<F, String>,
) -> Result<NewtonReport, String> {
let mut rep = NewtonReport::new();
let lam_min = 0.5f64.powi(opts.max_halvings as i32);
let mut f = pr.residual(&parts(z), opts.par)?;
let mut prev: Option<(f64, Vec<P::Scalar>, f64)> = None;
for _ in 0..opts.max_iter {
let fmax = max_abs::<P>(&f);
rep.fnorm.push(fmax);
if !fmax.is_finite() {
return Ok(rep);
}
if fmax <= opts.tol {
rep.converged = true;
return Ok(rep);
}
let lu = factor(&parts(z))?;
let dz = lu.try_solve_neg(&f)?;
let ndz = norm2::<P>(&dz);
let mut lam = match &prev {
None => opts.lambda0,
Some((n0, bar0, lam0)) => {
let diff: Vec<P::Scalar> = bar0.iter().zip(&dz).map(|(&a, &b)| a - b).collect();
let mu = n0 * norm2::<P>(bar0) * lam0 / (norm2::<P>(&diff) * ndz);
if mu.is_nan() {
1.0
} else {
mu.min(1.0)
}
}
};
let mut raised = false;
loop {
if lam.is_nan() || lam < lam_min || lam == 0.0 {
rep.fnorm.push(fmax);
return Ok(rep);
}
let zt = axpy::<P>(&parts(z), &dz, lam);
let ft = pr.residual(&parts(&zt), opts.par)?;
let bar = lu.try_solve_neg(&ft)?;
let nbar = norm2::<P>(&bar);
let theta = nbar / ndz;
let rest = P::from_dd(DD::from_f64(1.0 - lam));
let w: Vec<P::Scalar> = bar.iter().zip(&dz).map(|(&b, &d)| b - d * rest).collect();
let mu = 0.5 * ndz * lam * lam / norm2::<P>(&w);
if theta.is_nan() || theta >= 1.0 - lam / 4.0 {
lam = mu.min(lam / 2.0);
continue;
}
let lam_new = mu.min(1.0);
if !raised && lam < 1.0 && lam_new >= 4.0 * lam {
raised = true;
lam = lam_new;
continue;
}
rep.scale.push(lam);
rep.theta.push(theta);
rep.dz_bar.push(nbar);
*z = zt;
f = ft;
if opts.tol_dz > 0.0 && lam == 1.0 && nbar <= opts.tol_dz {
rep.fnorm.push(max_abs::<P>(&f));
rep.converged = true;
return Ok(rep);
}
prev = Some((ndz, bar, lam));
break;
}
}
let fmax = max_abs::<P>(&f);
rep.fnorm.push(fmax);
rep.converged = fmax <= opts.tol;
Ok(rep)
}
fn newton_residual<P: Precision<Native>, Pr: Problem<P> + ?Sized, F: Factored<P>>(
pr: &Pr,
z: &mut Vec<Vec<f64>>,
opts: &NewtonOpts,
factor: impl Fn(&[&[f64]]) -> Result<F, String>,
) -> Result<NewtonReport, String> {
let mut rep = NewtonReport::new();
let mut f = pr.residual(&parts(z), opts.par)?;
let mut fn0 = max_abs::<P>(&f);
for _ in 0..opts.max_iter {
rep.fnorm.push(fn0);
if !fn0.is_finite() {
return Ok(rep);
}
if fn0 <= opts.tol {
rep.converged = true;
return Ok(rep);
}
let dz = factor(&parts(z))?.try_solve_neg(&f)?;
let mut s = 1.0;
let (mut zn, mut ft, mut fnn);
let mut h = 0;
loop {
zn = axpy::<P>(&parts(z), &dz, s);
ft = pr.residual(&parts(&zn), opts.par)?;
fnn = max_abs::<P>(&ft);
if fnn < fn0 || h == opts.max_halvings {
break;
}
s *= 0.5;
h += 1;
}
if !fnn.is_finite() {
rep.fnorm.push(fnn);
return Ok(rep);
}
rep.scale.push(s);
*z = zn;
f = ft;
fn0 = fnn;
}
rep.fnorm.push(fn0);
rep.converged = fn0 <= opts.tol;
Ok(rep)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::{Double, DD};
#[test]
fn norm2_does_not_overflow() {
let v = [DD::from_f64(1e160), DD::from_f64(1e160)];
let n = norm2::<Double>(&v);
assert!((n / (1e160 * 2f64.sqrt()) - 1.0).abs() < 1e-15, "norm {n}");
let naive = v.iter().map(|x| x.hi * x.hi).sum::<f64>().sqrt();
assert!(naive.is_infinite());
}
#[test]
fn norm2_nan_and_zero() {
assert!(norm2::<Double>(&[DD::from_f64(1.0), DD::from_f64(f64::NAN)]).is_nan());
assert_eq!(norm2::<Double>(&[DD::ZERO, DD::ZERO]), 0.0);
}
}