use multisolver::multidouble::linalg::ld_for;
use multisolver::newton::NewtonOpts;
use multisolver::prec::{nan_max, parts};
use multisolver::subspace::{newton_deflated, weak_subspace, Factors};
use multisolver::{Double, Problem, DD};
const N: usize = 8;
fn householder(ones: [usize; 4]) -> Vec<Vec<DD>> {
(0..N)
.map(|i| {
(0..N)
.map(|j| {
let id = if i == j { 1.0 } else { 0.0 };
let vv = if ones.contains(&i) && ones.contains(&j) {
0.5
} else {
0.0
};
DD::from_f64(id - vv)
})
.collect()
})
.collect()
}
fn mul(a: &[Vec<DD>], b: &[Vec<DD>]) -> Vec<Vec<DD>> {
(0..N)
.map(|i| {
(0..N)
.map(|j| (0..N).fold(DD::ZERO, |t, k| t + a[i][k] * b[k][j]))
.collect()
})
.collect()
}
fn sigma() -> Vec<f64> {
(0..N)
.map(|i| match i {
0 => 2f64.powi(-40),
1 => 2f64.powi(-30),
_ => 1.0 + 0.5 * (i - 2) as f64,
})
.collect()
}
fn planted() -> (Vec<Vec<DD>>, Vec<Vec<DD>>) {
let r = mul(&householder([0, 1, 2, 3]), &householder([2, 3, 4, 5]));
let s = mul(&householder([1, 2, 5, 6]), &householder([0, 3, 4, 7]));
let sg = sigma();
let a = (0..N)
.map(|i| {
(0..N)
.map(|j| (0..N).fold(DD::ZERO, |t, k| t + r[i][k] * DD::from_f64(sg[k]) * s[j][k]))
.collect()
})
.collect();
(a, s)
}
struct Lin {
a: Vec<Vec<DD>>,
b: Vec<DD>,
}
impl Problem<Double> for Lin {
fn len(&self) -> usize {
N
}
fn residual(&self, z: &[&[f64]], _par: bool) -> Result<Vec<DD>, String> {
Ok((0..N)
.map(|i| (0..N).fold(DD::ZERO, |t, j| t + self.a[i][j] * DD::new(z[0][j], z[1][j])) - self.b[i])
.collect())
}
fn jacobian(&self, _z: &[&[f64]], _par: bool) -> Result<(Vec<Vec<f64>>, usize), String> {
let ld = ld_for(N);
let mut c = vec![vec![0.0; ld * N]; 2];
for (i, row) in self.a.iter().enumerate() {
for (j, v) in row.iter().enumerate() {
(c[0][j * ld + i], c[1][j * ld + i]) = (v.hi, v.lo);
}
}
Ok((c, ld))
}
}
fn lin() -> (Lin, Vec<Vec<f64>>) {
let (a, _) = planted();
let zs: Vec<DD> = (0..N).map(|i| DD::from_f64(1.0 + i as f64 / 8.0)).collect();
let b = (0..N)
.map(|i| (0..N).fold(DD::ZERO, |t, j| t + a[i][j] * zs[j]))
.collect();
(
Lin { a, b },
vec![zs.iter().map(|v| v.hi).collect(), zs.iter().map(|v| v.lo).collect()],
)
}
fn off_span(x: &[f64], s: &[Vec<DD>]) -> f64 {
let cols: Vec<Vec<f64>> = (0..2).map(|k| (0..N).map(|i| s[i][k].hi).collect()).collect();
let mut r = x.to_vec();
for col in &cols {
let c: f64 = col.iter().zip(x).map(|(a, b)| a * b).sum();
r.iter_mut().zip(col).for_each(|(ri, ci)| *ri -= c * ci);
}
r.iter().map(|v| v * v).sum::<f64>().sqrt()
}
fn weak(iters: usize) -> (Vec<Vec<f64>>, Vec<f64>) {
let (pr, zs) = lin();
let f = Factors::<Double>::new(&pr, &parts(&zs), false).unwrap();
weak_subspace::<Double>(&f, 2, iters, 7)
}
fn weak_errors(basis: &[Vec<f64>], sg: &[f64]) -> (f64, f64, f64) {
let (_, s) = planted();
let d = basis.iter().map(|b| off_span(b, &s)).fold(0.0, nan_max);
let want = sigma();
(d, (sg[0] / want[0] - 1.0).abs(), (sg[1] / want[1] - 1.0).abs())
}
fn weak_checks((d, e0, e1): (f64, f64, f64)) -> [bool; 3] {
[d <= 1e-12, e0 <= 1e-10, e1 <= 1e-10]
}
#[test]
fn weak_subspace_finds_the_planted_directions() {
let (basis, sg) = weak(4);
let (d, e0, e1) = weak_errors(&basis, &sg);
println!("weak subspace: off the span {d:.3e}, sigma errors {e0:.3e} {e1:.3e}");
assert_eq!(weak_checks((d, e0, e1)), [true; 3]);
let (b0, sg0) = weak(0);
let (d, _, _) = weak_errors(&b0, &sg0);
println!("control, no iterations: off the span {d:.3e}");
assert!(
d > 1e-2 && !weak_checks(weak_errors(&b0, &sg0))[0],
"control did not fire"
);
let off: Vec<f64> = sg.iter().map(|v| v * (1.0 + 1e-8)).collect();
let e = weak_errors(&basis, &off);
println!(
"control, singular values off by 1e-8: sigma errors {:.3e} {:.3e}",
e.1, e.2
);
assert_eq!(weak_checks(e), [true, false, false], "control did not fire");
}
const SCALED: [f64; N] = [1.0, 2.0, 1000.0, 1001.0, 1002.0, 1003.0, 1004.0, 1005.0];
struct Scaled(f64);
impl Problem<Double> for Scaled {
fn len(&self) -> usize {
N
}
fn residual(&self, z: &[&[f64]], _par: bool) -> Result<Vec<DD>, String> {
Ok((0..N)
.map(|i| DD::from_f64(self.0 * SCALED[i]) * (DD::new(z[0][i], z[1][i]) - DD::ONE))
.collect())
}
fn jacobian(&self, _z: &[&[f64]], _par: bool) -> Result<(Vec<Vec<f64>>, usize), String> {
let ld = ld_for(N);
let mut c = vec![vec![0.0; ld * N]; 2];
for i in 0..N {
c[0][i * ld + i] = self.0 * SCALED[i];
}
Ok((c, ld))
}
}
#[test]
fn weak_subspace_at_extreme_scales() {
let zero = vec![vec![0.0; N]; 2];
for scale in [1e-100, 1e100] {
let f = Factors::<Double>::new(&Scaled(scale), &parts(&zero), false).unwrap();
let run = |iters: usize| {
let (basis, sg) = weak_subspace::<Double>(&f, 2, iters, 7);
let d = basis
.iter()
.map(|b| b[2..].iter().map(|v| v * v).sum::<f64>().sqrt())
.fold(0.0, nan_max);
(d, (sg[0] / scale - 1.0).abs(), (sg[1] / (2.0 * scale) - 1.0).abs())
};
let (d, e0, e1) = run(4);
println!("s {scale:e}: off the span {d:.3e}, sigma errors {e0:.3e} {e1:.3e}");
assert_eq!(weak_checks((d, e0, e1)), [true; 3]);
let (d, _, _) = run(0);
println!("control, no iterations: off the span {d:.3e}");
assert!(d > 1e-2, "control did not fire");
}
}
fn transpose_residual(a: &[Vec<DD>], y: &[DD], k: usize) -> f64 {
let amax = a.iter().flatten().map(|v| v.hi.abs()).fold(0.0, nan_max);
let ymax = y.iter().map(|v| v.hi.abs()).fold(0.0, nan_max);
(0..N)
.map(|j| {
let aty = (0..N).fold(DD::ZERO, |t, i| t + a[i][j] * y[i]);
(aty - if j == k { DD::ONE } else { DD::ZERO }).hi.abs()
})
.fold(0.0, nan_max)
/ (amax * ymax)
}
fn sensitivity(k: usize, transpose: bool) -> (Lin, Vec<DD>) {
let (pr, zs) = lin();
let f = Factors::<Double>::new(&pr, &parts(&zs), false).unwrap();
let y = if transpose {
f.sensitivity(k)
} else {
let mut e = vec![DD::ZERO; N];
e[k] = DD::ONE;
f.solve(&e)
};
(pr, y)
}
#[test]
fn sensitivity_solves_the_transpose() {
let accurate = |e: f64| e <= 1e-30;
let e = (0..N)
.map(|k| {
let (pr, y) = sensitivity(k, true);
transpose_residual(&pr.a, &y, k)
})
.fold(0.0, nan_max);
let (pr, y) = sensitivity(3, false);
let c = transpose_residual(&pr.a, &y, 3);
println!("sensitivity: residual {e:.3e}; control, J^-1 e_k {c:.3e}");
assert!(accurate(e));
assert!(c > 1e-3, "control did not fire");
let (pr, mut y) = sensitivity(3, true);
y[5] = DD::from_f64(f64::NAN);
let n = transpose_residual(&pr.a, &y, 3);
println!("control, one entry NaN: {n:.3e}");
assert!(!accurate(n), "NaN control did not fire");
}
#[test]
fn deflated_newton_never_moves_along_the_subspace() {
let (pr, zs) = lin();
let (_, s) = planted();
let f = Factors::<Double>::new(&pr, &parts(&zs), false).unwrap();
let (basis, _) = weak_subspace::<Double>(&f, 2, 6, 7);
let start: Vec<Vec<f64>> = vec![
zs[0]
.iter()
.enumerate()
.map(|(i, v)| v + 1e-3 * (1.0 + i as f64 / 3.0))
.collect(),
zs[1].clone(),
];
let measure = |z: &[Vec<f64>]| {
let dz: Vec<f64> = (0..N)
.map(|i| (DD::new(z[0][i], z[1][i]) - DD::new(start[0][i], start[1][i])).hi)
.collect();
let de: Vec<f64> = (0..N)
.map(|i| (DD::new(z[0][i], z[1][i]) - DD::new(zs[0][i], zs[1][i])).hi)
.collect();
let along: f64 = (0..2)
.map(|k| (0..N).map(|i| s[i][k].hi * dz[i]).sum::<f64>().abs())
.fold(0.0, nan_max);
(along, off_span(&de, &s))
};
let checks = |(along, off): (f64, f64)| [along <= 1e-25, off <= 1e-25];
let opts = NewtonOpts {
tol: 1e-28,
max_iter: 3,
..Default::default()
};
let mut z = start.clone();
newton_deflated::<Double, _>(&pr, &mut z, &opts, &basis).unwrap();
let (along, off) = measure(&z);
println!("deflated Newton: moved along the span {along:.3e}, left off the span {off:.3e}");
assert_eq!(checks((along, off)), [true; 2]);
let mut z = start.clone();
multisolver::newton::newton::<Double, _>(&pr, &mut z, &opts).unwrap();
let (along, off) = measure(&z);
println!("control, plain Newton: moved along the span {along:.3e}, left off it {off:.3e}");
assert!(
along > 1e-6 && checks((along, off)) == [false, true],
"control did not fire"
);
let (along, off) = measure(&start);
println!("control, the start: moved along the span {along:.3e}, left off it {off:.3e}");
assert_eq!(checks((along, off)), [true, false], "control did not fire");
}
#[test]
fn condition_estimate_of_the_planted_matrix() {
let (pr, zs) = lin();
let f = Factors::<Double>::new(&pr, &parts(&zs), false).unwrap();
let norm1 = (0..N)
.map(|j| (0..N).map(|i| pr.a[i][j].hi.abs()).sum::<f64>())
.fold(0.0, nan_max);
let exact = (0..N)
.map(|k| {
let mut e = vec![DD::ZERO; N];
e[k] = DD::ONE;
f.solve(&e).iter().map(|v| v.hi.abs()).sum::<f64>()
})
.fold(0.0, nan_max);
let est = f.inv_norm1();
let ok = |e: f64| e >= exact / 3.0 && e <= exact * (1.0 + 1e-12);
let norm_ok = |x: f64| (x / norm1 - 1.0).abs() <= 1e-15;
println!(
"||A||_1 {:.6e} (factors {:.6e}); ||A^-1||_1 {exact:.6e}, estimate {est:.6e}; cond1 {:.3e}",
norm1,
f.norm1,
f.cond1()
);
assert!(norm_ok(f.norm1) && ok(est));
assert!(!ok(4.0 * est) && !ok(est / 4.0), "control did not fire");
assert!(!norm_ok(2.0 * f.norm1), "norm control did not fire");
}
struct Diag {
d: f64,
n: usize,
}
impl Problem<Double> for Diag {
fn len(&self) -> usize {
self.n
}
fn residual(&self, z: &[&[f64]], _par: bool) -> Result<Vec<DD>, String> {
Ok((0..self.n)
.map(|i| DD::from_f64(self.d) * (DD::new(z[0][i], z[1][i]) - DD::ONE))
.collect())
}
fn jacobian(&self, _z: &[&[f64]], _par: bool) -> Result<(Vec<Vec<f64>>, usize), String> {
let ld = ld_for(self.n);
let mut c = vec![vec![0.0; ld * self.n]; 2];
for i in 0..self.n {
c[0][i * ld + i] = self.d;
}
Ok((c, ld))
}
}
#[test]
fn condition_estimate_near_overflow() {
let pr = Diag {
d: 2f64.powi(-1018),
n: 32,
};
let z = vec![vec![1.0; 32], vec![0.0; 32]];
let f = Factors::<Double>::new(&pr, &parts(&z), false).unwrap();
let ok = |inv: f64, cond: f64| (inv / 2f64.powi(1018) - 1.0).abs() <= 1e-15 && (cond - 1.0).abs() <= 1e-15;
let (inv, cond) = (f.inv_norm1(), f.cond1());
println!("2^-1018 I: ||J^-1||_1 {inv:e}, cond1 {cond}");
assert!(ok(inv, cond));
assert!(!ok(f64::INFINITY, cond), "inverse-norm control did not fire");
assert!(!ok(inv, f64::INFINITY), "condition control did not fire");
}