use crate::gcr::recip;
use crate::newton::{newton_with, Factored, NewtonOpts, NewtonReport};
use crate::prec::nan_max;
use crate::Problem;
use multidouble::dd::DD;
use multidouble::precision::Precision;
use multidouble::simd::Native;
use rayon::prelude::*;
pub struct Factors<P: Precision<Native>> {
pub n: usize,
pub lu: P::Lu,
pub lut: P::Lu,
pub norm1: f64,
}
impl<P: Precision<Native>> Factors<P> {
pub fn new<Pr: Problem<P> + ?Sized>(pr: &Pr, z: &[&[f64]], par: bool) -> Result<Self, String> {
let n = pr.len();
let (c, ld) = pr.jacobian(z, par)?;
let norm1 = (0..n)
.map(|j| c[0][j * ld..j * ld + n].iter().map(|v| v.abs()).sum::<f64>())
.fold(0.0, nan_max);
let mut ct = vec![vec![0.0; ld * n]; P::PARTS];
let row = |cq: &[f64], i: usize, col: &mut [f64]| {
for (j, x) in col[..n].iter_mut().enumerate() {
*x = cq[j * ld + i];
}
};
for (cq, tq) in c.iter().zip(ct.iter_mut()) {
if par {
tq.par_chunks_mut(ld)
.take(n)
.enumerate()
.for_each(|(i, col)| row(cq, i, col));
} else {
tq.chunks_mut(ld)
.take(n)
.enumerate()
.for_each(|(i, col)| row(cq, i, col));
}
}
let (lu, lut) = if par {
rayon::join(|| P::lu_factor(n, ld, c, par), || P::lu_factor(n, ld, ct, par))
} else {
(P::lu_factor(n, ld, c, par), P::lu_factor(n, ld, ct, par))
};
Ok(Factors {
n,
lu: lu?,
lut: lut?,
norm1,
})
}
pub fn inv_norm1(&self) -> f64 {
let n = self.n;
let l1 = |v: &[P::Scalar]| v.iter().map(|&x| P::to_dd(x).hi.abs()).sum::<f64>();
let scalar = |v: f64| P::from_dd(DD::from_f64(v));
let mut x: Vec<P::Scalar> = vec![scalar(1.0 / n as f64); n];
let mut est = 0.0f64;
let mut last = usize::MAX;
for it in 0..5 {
let y = self.solve(&x);
let e = l1(&y);
if it > 0 && e <= est {
break;
}
est = e;
let sgn: Vec<P::Scalar> = y
.iter()
.map(|&v| scalar(if P::to_dd(v).hi < 0.0 { -1.0 } else { 1.0 }))
.collect();
let z = self.solve_t(&sgn);
let za: Vec<f64> = z.iter().map(|&v| P::to_dd(v).hi.abs()).collect();
let j = (0..n).max_by(|&a, &b| za[a].total_cmp(&za[b])).unwrap_or(0);
let zx: f64 = z.iter().zip(&x).map(|(&a, &b)| P::to_dd(a * b).hi).sum();
if (it > 0 && za[j] <= zx) || j == last {
break;
}
last = j;
x = vec![P::ZERO; n];
x[j] = P::ONE;
}
if n > 1 {
let sc = 2.0 / (3 * n) as f64;
let b: Vec<P::Scalar> = (0..n)
.map(|i| {
let v = sc * (1.0 + i as f64 / (n - 1) as f64);
scalar(if i % 2 == 0 { v } else { -v })
})
.collect();
est = est.max(l1(&self.solve(&b)));
}
est
}
pub fn cond1(&self) -> f64 {
self.norm1 * self.inv_norm1()
}
pub fn solve(&self, b: &[P::Scalar]) -> Vec<P::Scalar> {
let mut x = b.to_vec();
P::lu_solve(&self.lu, &mut x);
x
}
pub fn solve_t(&self, b: &[P::Scalar]) -> Vec<P::Scalar> {
let mut x = b.to_vec();
P::lu_solve(&self.lut, &mut x);
x
}
fn normal(&self, v: &[f64]) -> Vec<f64> {
let b: Vec<P::Scalar> = v.iter().map(|&x| P::from_dd(DD::from_f64(x))).collect();
self.solve(&self.solve_t(&b)).iter().map(|&x| P::to_dd(x).hi).collect()
}
pub fn sensitivity(&self, k: usize) -> Vec<P::Scalar> {
let mut e = vec![P::ZERO; self.n];
e[k] = P::ONE;
self.solve_t(&e)
}
}
fn wave(state: &mut u64) -> f64 {
*state ^= *state << 13;
*state ^= *state >> 7;
*state ^= *state << 17;
(*state >> 11) as f64 / (1u64 << 52) as f64 - 1.0
}
fn dot(a: &[f64], b: &[f64]) -> f64 {
a.iter().zip(b).map(|(x, y)| x * y).sum()
}
fn norm(v: &[f64]) -> f64 {
let m = v.iter().map(|x| x.abs()).fold(0.0, nan_max);
if m == 0.0 || !m.is_finite() {
return m;
}
m * v.iter().map(|&x| (x / m) * (x / m)).sum::<f64>().sqrt()
}
fn orthonormalize(v: &mut [Vec<f64>]) {
for _ in 0..2 {
for j in 0..v.len() {
for i in 0..j {
let c = dot(&v[i], &v[j]);
let (head, tail) = v.split_at_mut(j);
tail[0].iter_mut().zip(&head[i]).for_each(|(x, y)| *x -= c * y);
}
let nrm = norm(&v[j]);
v[j].iter_mut().for_each(|x| *x /= nrm);
}
}
}
fn jacobi(mut a: Vec<Vec<f64>>) -> (Vec<f64>, Vec<Vec<f64>>) {
let w = a.len();
let mut q: Vec<Vec<f64>> = (0..w)
.map(|i| (0..w).map(|j| (i == j) as u8 as f64).collect())
.collect();
for _ in 0..100 {
let s = a.iter().flatten().fold(0.0f64, |m, &x| m.max(x.abs()));
if s == 0.0 || !s.is_finite() {
break;
}
let sq = |x: f64| (x / s) * (x / s);
let off: f64 = (0..w)
.flat_map(|i| (0..w).filter(move |&j| j != i).map(move |j| (i, j)))
.map(|(i, j)| sq(a[i][j]))
.sum();
let diag: f64 = (0..w).map(|i| sq(a[i][i])).sum();
if off <= 1e-32 * diag {
break;
}
for p in 0..w {
for r in p + 1..w {
if a[p][r] == 0.0 {
continue;
}
let th = (a[r][r] - a[p][p]) / (2.0 * a[p][r]);
let t = th.signum() / (th.abs() + (th * th + 1.0).sqrt());
let t = if th == 0.0 { 1.0 } else { t };
let c = 1.0 / (t * t + 1.0).sqrt();
let s = t * c;
for row in a.iter_mut() {
let (akp, akr) = (row[p], row[r]);
row[p] = c * akp - s * akr;
row[r] = s * akp + c * akr;
}
let (lo, hi) = a.split_at_mut(r);
for (x, y) in lo[p].iter_mut().zip(hi[0].iter_mut()) {
let (apk, ark) = (*x, *y);
*x = c * apk - s * ark;
*y = s * apk + c * ark;
}
for row in q.iter_mut() {
let (qp, qr) = (row[p], row[r]);
row[p] = c * qp - s * qr;
row[r] = s * qp + c * qr;
}
}
}
}
((0..w).map(|i| a[i][i]).collect(), q)
}
pub fn weak_subspace<P: Precision<Native>>(
f: &Factors<P>,
w: usize,
iters: usize,
seed: u64,
) -> (Vec<Vec<f64>>, Vec<f64>) {
let mut st = seed.max(1);
let mut v: Vec<Vec<f64>> = (0..w).map(|_| (0..f.n).map(|_| wave(&mut st)).collect()).collect();
orthonormalize(&mut v);
for _ in 0..iters {
v = v.par_iter().map(|x| f.normal(x)).collect();
orthonormalize(&mut v);
}
let av: Vec<Vec<f64>> = v.par_iter().map(|x| f.normal(x)).collect();
let t: Vec<Vec<f64>> = (0..w).map(|i| (0..w).map(|j| dot(&v[i], &av[j])).collect()).collect();
let (lam, q) = jacobi(t);
let mut order: Vec<usize> = (0..w).collect();
order.sort_by(|&a, &b| lam[b].total_cmp(&lam[a]));
let basis = order
.iter()
.map(|&k| (0..f.n).map(|i| (0..w).map(|j| v[j][i] * q[j][k]).sum()).collect())
.collect();
let sigma = order.iter().map(|&k| 1.0 / lam[k].sqrt()).collect();
(basis, sigma)
}
pub fn remove<P: Precision<Native>>(x: &mut [P::Scalar], basis: &[Vec<f64>]) {
let dot = |a: &[P::Scalar], b: &[P::Scalar]| P::dot(a.iter().copied().zip(b.iter().copied()));
let mut qs: Vec<(Vec<P::Scalar>, P::Scalar)> = Vec::with_capacity(basis.len());
for b in basis {
let m = b.iter().map(|v| v.abs()).fold(0.0, nan_max);
let sc = if m > 0.0 && m.is_finite() {
2f64.powi(-(m.log2().floor() as i32).clamp(-1000, 1000))
} else {
1.0
};
let mut q: Vec<P::Scalar> = b.iter().map(|&v| P::from_dd(DD::from_f64(v * sc))).collect();
for (p, inv) in &qs {
let c = dot(p, &q) * *inv;
q.iter_mut().zip(p).for_each(|(qi, &pi)| *qi = *qi - c * pi);
}
let inv = recip::<P>(dot(&q, &q));
qs.push((q, inv));
}
for (q, inv) in &qs {
let c = dot(q, x) * *inv;
x.iter_mut().zip(q).for_each(|(xi, &qi)| *xi = *xi - c * qi);
}
}
pub struct Deflated<F> {
pub inner: F,
pub basis: Vec<Vec<f64>>,
}
impl<P: Precision<Native>, F: Factored<P>> Factored<P> for Deflated<F> {
fn solve_neg(&self, r: &[P::Scalar]) -> Vec<P::Scalar> {
let mut x = self.inner.solve_neg(r);
remove::<P>(&mut x, &self.basis);
x
}
fn try_solve_neg(&self, r: &[P::Scalar]) -> Result<Vec<P::Scalar>, String> {
let mut x = self.inner.try_solve_neg(r)?;
remove::<P>(&mut x, &self.basis);
Ok(x)
}
}
pub fn newton_deflated<P: Precision<Native>, Pr: Problem<P> + ?Sized>(
pr: &Pr,
z: &mut Vec<Vec<f64>>,
opts: &NewtonOpts,
basis: &[Vec<f64>],
) -> Result<NewtonReport, String> {
newton_with::<P, Pr, _>(pr, z, opts, |z| {
Ok(Deflated {
inner: crate::newton::exact::<P, Pr>(pr, z, opts.par)?,
basis: basis.to_vec(),
})
})
}
#[cfg(test)]
mod tests {
use super::*;
fn jacobi_checks(lam: &[f64], q: &[Vec<f64>], s: f64) -> [bool; 2] {
let mut l: Vec<f64> = lam.iter().map(|&x| x / s).collect();
l.sort_by(f64::total_cmp);
let k = if lam[0] < lam[1] { 0 } else { 1 };
[
(l[0] - 1.0).abs() < 1e-15 && (l[1] - 3.0).abs() < 1e-15,
(q[0][k] + q[1][k]).abs() < 1e-15,
]
}
#[test]
fn jacobi_on_a_known_matrix() {
for s in [1.0, 1e200, 1e-200] {
let (lam, q) = jacobi(vec![vec![2.0 * s, s], vec![s, 2.0 * s]]);
assert_eq!(jacobi_checks(&lam, &q, s), [true; 2], "s {s:e}: {lam:?} {q:?}");
}
let (lam, q) = jacobi(vec![vec![2.0, 1.0], vec![1.0, 2.0]]);
let wrong: Vec<f64> = lam.iter().map(|&x| if x > 2.0 { x + 3e-12 } else { x }).collect();
assert_eq!(
jacobi_checks(&wrong, &q, 1.0),
[false, true],
"eigenvalue control did not fire"
);
let id = vec![vec![1.0, 0.0], vec![0.0, 1.0]];
assert_eq!(
jacobi_checks(&lam, &id, 1.0),
[true, false],
"eigenvector control did not fire"
);
}
#[test]
fn orthonormalize_at_extreme_scales() {
let check =
|v: &[Vec<f64>]| (0..2).all(|i| (0..2).all(|j| (dot(&v[i], &v[j]) - (i == j) as u8 as f64).abs() < 1e-15));
for s in [1e200, 1e-200] {
let start = vec![vec![s, 2.0 * s, 0.0], vec![s, 0.0, 3.0 * s]];
let mut v = start.clone();
orthonormalize(&mut v);
assert!(check(&v), "s {s:e}: {v:?}");
assert!(!check(&start), "control did not fire");
}
}
fn along<P: Precision<Native>>(x: &[P::Scalar], basis: &[Vec<f64>]) -> f64 {
basis
.iter()
.map(|b| {
P::to_dd(P::dot(
b.iter().map(|&v| P::from_dd(DD::from_f64(v))).zip(x.iter().copied()),
))
.hi
.abs()
})
.fold(0.0, nan_max)
}
#[test]
fn remove_is_exact_in_p_for_an_f64_basis() {
let basis = vec![
vec![1.0 / 2f64.sqrt(), 1.0 / 2f64.sqrt(), 0.0],
vec![1.0 / 3f64.sqrt(), -1.0 / 3f64.sqrt(), 1.0 / 3f64.sqrt()],
];
let e = [1.0, -1.0, -2.0];
let x0: Vec<DD> = (0..3)
.map(|i| {
DD::from_f64(3.0) * DD::from_f64(basis[0][i]) - DD::from_f64(2.0) * DD::from_f64(basis[1][i])
+ DD::from_f64(e[i])
})
.collect();
let checks = |x: &[DD]| {
let rest = (0..3).map(|i| (x[i] - DD::from_f64(e[i])).hi.abs()).fold(0.0, nan_max);
[along::<crate::Double>(x, &basis) <= 1e-30, rest <= 1e-15]
};
for scale in [1.0, 2f64.powi(-600), 2f64.powi(600)] {
let scaled: Vec<Vec<f64>> = basis.iter().map(|b| b.iter().map(|v| v * scale).collect()).collect();
let mut x = x0.clone();
remove::<crate::Double>(&mut x, &scaled);
assert_eq!(checks(&x), [true; 2], "scale {scale:e}: {x:?}");
}
assert!(!checks(&x0)[0], "control did not fire");
assert_eq!(
checks(&[DD::from_f64(f64::NAN); 3]),
[false; 2],
"NaN control did not fire"
);
}
}