use crate::newton::{newton_with, norm2, Factored, NewtonOpts, NewtonReport};
use crate::prec::parts;
use crate::Jvp;
use multidouble::dd::DD;
use multidouble::precision::Precision;
use multidouble::simd::Native;
use std::cell::{Cell, RefCell};
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Coef {
Full,
F64,
}
#[derive(Clone, Copy, Debug)]
pub struct GcrOpts {
pub max_products: usize,
pub step_tol: f64,
pub confirm: usize,
pub coef: Coef,
pub nu: f64,
}
impl Default for GcrOpts {
fn default() -> Self {
GcrOpts {
max_products: 30,
step_tol: 1e-28,
confirm: 1,
coef: Coef::Full,
nu: 0.9,
}
}
}
#[derive(Clone, Debug, Default)]
pub struct GcrInfo {
pub products: usize,
pub changes: Vec<f64>,
pub converged: bool,
}
pub(crate) fn recip<P: Precision<Native>>(a: P::Scalar) -> P::Scalar {
let mut x = P::from_dd(DD::from_f64(1.0 / P::to_dd(a).hi));
let steps = P::PARTS.trailing_zeros() as usize + 1;
for _ in 0..steps {
x = x + x * (P::ONE - a * x);
}
x
}
fn dot<P: Precision<Native>>(a: &[P::Scalar], b: &[P::Scalar]) -> P::Scalar {
P::dot(a.iter().copied().zip(b.iter().copied()))
}
fn dot64<P: Precision<Native>>(a: &[P::Scalar], b: &[P::Scalar]) -> f64 {
a.iter().zip(b).map(|(&x, &y)| P::to_dd(x).hi * P::to_dd(y).hi).sum()
}
fn axpy<P: Precision<Native>>(c: P::Scalar, x: &[P::Scalar], y: &mut [P::Scalar]) {
for (yi, &xi) in y.iter_mut().zip(x) {
*yi = *yi + c * xi;
}
}
struct Dir<P: Precision<Native>> {
u: Vec<P::Scalar>,
w: Vec<P::Scalar>,
inv: P::Scalar,
}
pub fn gcr<P: Precision<Native>>(
mut apply: impl FnMut(&[P::Scalar]) -> Result<Vec<P::Scalar>, String>,
precond: impl Fn(&[P::Scalar]) -> Result<Vec<P::Scalar>, String>,
b: &[P::Scalar],
opts: &GcrOpts,
) -> Result<(Vec<P::Scalar>, GcrInfo), String> {
let n = b.len();
let mut x = vec![P::ZERO; n];
let mut r = b.to_vec();
let mut dirs: Vec<Dir<P>> = Vec::new();
let mut info = GcrInfo::default();
let mut run = 0;
let mut rn = norm2::<P>(&r);
let unit = match opts.coef {
Coef::Full => 0.5f64.powi(52 * P::PARTS as i32),
Coef::F64 => 0.5f64.powi(52),
};
let floor = rn * opts.step_tol.max(n as f64 * unit);
let mut fell = true;
loop {
if rn == 0.0 {
info.converged = true;
break;
}
if rn.is_nan() || info.products >= opts.max_products {
break;
}
let src = match dirs.last() {
Some(d) if !fell => &d.w,
_ => &r,
};
let mut u = precond(src)?;
let mut w = apply(&u)?;
info.products += 1;
for _ in 0..2 {
for d in &dirs {
let beta = match opts.coef {
Coef::Full => dot::<P>(&d.w, &w) * d.inv,
Coef::F64 => P::from_dd(DD::from_f64(dot64::<P>(&d.w, &w))),
};
axpy::<P>(-beta, &d.w, &mut w);
axpy::<P>(-beta, &d.u, &mut u);
}
}
let nw = norm2::<P>(&w);
if nw.is_nan() || nw <= 0.0 {
break;
}
let s = P::from_dd(DD::from_f64(1.0 / nw));
w.iter_mut().for_each(|v| *v = *v * s);
u.iter_mut().for_each(|v| *v = *v * s);
let (c, inv) = match opts.coef {
Coef::Full => {
let inv = recip::<P>(dot::<P>(&w, &w));
(dot::<P>(&w, &r) * inv, inv)
}
Coef::F64 => (P::from_dd(DD::from_f64(dot64::<P>(&w, &r))), P::ONE),
};
axpy::<P>(c, &u, &mut x);
axpy::<P>(-c, &w, &mut r);
let rn1 = norm2::<P>(&r);
fell = rn1 <= opts.nu * rn;
let counts = fell || (rn1 <= floor && P::to_dd(c).hi != 0.0);
rn = rn1;
let ch = P::to_dd(c).hi.abs() * norm2::<P>(&u) / norm2::<P>(&x).max(1e-300);
info.changes.push(ch);
dirs.push(Dir { u, w, inv });
run = if dirs.len() > 1 && counts && ch <= opts.step_tol {
run + 1
} else {
0
};
if run >= opts.confirm {
info.converged = true;
break;
}
}
Ok((x, info))
}
pub struct Refined<'a, P: Precision<Native>, Pr: Jvp<P> + ?Sized, F: Factored<P>> {
pub pr: &'a Pr,
pub z: Vec<Vec<f64>>,
pub inner: F,
pub opts: GcrOpts,
pub par: bool,
pub products: Cell<usize>,
pub last: RefCell<GcrInfo>,
_p: std::marker::PhantomData<P>,
}
impl<'a, P: Precision<Native>, Pr: Jvp<P> + ?Sized, F: Factored<P>> Refined<'a, P, Pr, F> {
pub fn new(pr: &'a Pr, z: &[&[f64]], inner: F, opts: GcrOpts, par: bool) -> Self {
Refined {
pr,
z: z.iter().map(|p| p.to_vec()).collect(),
inner,
opts,
par,
products: Cell::new(0),
last: RefCell::new(GcrInfo::default()),
_p: std::marker::PhantomData,
}
}
}
impl<P: Precision<Native>, Pr: Jvp<P> + ?Sized, F: Factored<P>> Factored<P> for Refined<'_, P, Pr, F> {
fn solve_neg(&self, r: &[P::Scalar]) -> Vec<P::Scalar> {
self.try_solve_neg(r).expect("Refined::solve_neg")
}
fn try_solve_neg(&self, r: &[P::Scalar]) -> Result<Vec<P::Scalar>, String> {
let z = parts(&self.z);
let b: Vec<P::Scalar> = r.iter().map(|&v| -v).collect();
let apply = |u: &[P::Scalar]| {
let up: Vec<Vec<f64>> = (0..P::PARTS)
.map(|q| u.iter().map(|&v| P::part(v, q)).collect())
.collect();
self.pr.jvp(&z, &parts(&up), self.par)
};
let precond = |v: &[P::Scalar]| -> Result<Vec<P::Scalar>, String> {
Ok(self.inner.try_solve_neg(v)?.into_iter().map(|x| -x).collect())
};
let (x, info) = gcr::<P>(apply, precond, &b, &self.opts)?;
self.products.set(self.products.get() + info.products);
*self.last.borrow_mut() = info;
Ok(x)
}
}
pub fn newton_refined<P: Precision<Native>, Pr: Jvp<P> + ?Sized, F: Factored<P>>(
pr: &Pr,
z: &mut Vec<Vec<f64>>,
opts: &NewtonOpts,
gcr_opts: &GcrOpts,
factor: impl Fn(&[&[f64]]) -> Result<F, String>,
) -> Result<(NewtonReport, usize), String> {
let products = Cell::new(0);
let refined = |z: &[&[f64]]| -> Result<CountOnDrop<'_, P, Pr, F>, String> {
Ok(CountOnDrop(
Refined::new(pr, z, factor(z)?, *gcr_opts, opts.par),
&products,
))
};
let rep = newton_with::<P, Pr, _>(pr, z, opts, refined)?;
Ok((rep, products.get()))
}
struct CountOnDrop<'a, P: Precision<Native>, Pr: Jvp<P> + ?Sized, F: Factored<P>>(
Refined<'a, P, Pr, F>,
&'a Cell<usize>,
);
impl<P: Precision<Native>, Pr: Jvp<P> + ?Sized, F: Factored<P>> Drop for CountOnDrop<'_, P, Pr, F> {
fn drop(&mut self) {
self.1.set(self.1.get() + self.0.products.get());
}
}
impl<P: Precision<Native>, Pr: Jvp<P> + ?Sized, F: Factored<P>> Factored<P> for CountOnDrop<'_, P, Pr, F> {
fn solve_neg(&self, r: &[P::Scalar]) -> Vec<P::Scalar> {
self.0.solve_neg(r)
}
fn try_solve_neg(&self, r: &[P::Scalar]) -> Result<Vec<P::Scalar>, String> {
self.0.try_solve_neg(r)
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::{Double, Octo, Quad};
#[test]
fn recip_reaches_the_precision() {
let e2 = (DD::from_f64(3.0) * recip::<Double>(DD::from_f64(3.0)) - DD::ONE)
.hi
.abs();
assert!(e2 < 2f64.powi(-104), "double-double {e2:e}");
let q = recip::<Quad>(<Quad as Precision<Native>>::from_dd(DD::from_f64(3.0)));
let eq = <Quad as Precision<Native>>::to_dd(
<Quad as Precision<Native>>::from_dd(DD::from_f64(3.0)) * q - <Quad as Precision<Native>>::ONE,
)
.hi
.abs();
assert!(eq < 2f64.powi(-208), "quad-double {eq:e}");
let o = recip::<Octo>(<Octo as Precision<Native>>::from_dd(DD::from_f64(3.0)));
let eo = <Octo as Precision<Native>>::to_dd(
<Octo as Precision<Native>>::from_dd(DD::from_f64(3.0)) * o - <Octo as Precision<Native>>::ONE,
)
.hi
.abs();
assert!(eo < 2f64.powi(-416), "octo-double {eo:e}");
let x0 = DD::from_f64(1.0 / 3.0);
assert!(
(DD::from_f64(3.0) * x0 - DD::ONE).hi.abs() > 2f64.powi(-104),
"control did not fire"
);
}
}