use multisolver::gcr::{gcr, Coef, GcrOpts};
use multisolver::multidouble::linalg::ld_for;
use multisolver::prec::nan_max;
use multisolver::{Double, Native, Precision, Quad, DD};
const N: usize = 20;
#[allow(clippy::type_complexity)]
fn system<P: Precision<Native>>() -> (Vec<Vec<P::Scalar>>, Vec<P::Scalar>, Vec<P::Scalar>) {
let a: Vec<Vec<P::Scalar>> = (0..N)
.map(|i| {
(0..N)
.map(|j| {
let v = if i == j {
4.0 + i as f64 / 10.0
} else {
0.1 * ((7 * i + 3 * j) as f64).sin()
};
P::from_dd(DD::new(v, v * 1e-17 * (1.0 + (i * N + j) as f64 / 400.0)))
})
.collect()
})
.collect();
let xs: Vec<P::Scalar> = (0..N)
.map(|i| P::from_dd(DD::from_f64(1.0 + (i as f64).sin() / 3.0)))
.collect();
let b = a
.iter()
.map(|row| P::dot(row.iter().copied().zip(xs.iter().copied())))
.collect();
(a, b, xs)
}
fn solve<P: Precision<Native>>(coef: Coef, perturb: f64, step_tol: f64) -> (f64, usize, bool) {
let (a, b, xs) = system::<P>();
let ld = ld_for(N);
let mut c = vec![vec![0.0; ld * N]; P::PARTS];
for (i, row) in a.iter().enumerate() {
for (j, &v) in row.iter().enumerate() {
c[0][j * ld + i] = P::part(v, 0);
}
}
let m = P::lu_factor(N, ld, c, false).unwrap();
let mut ap = a.clone();
ap[3][5] = ap[3][5] * P::from_dd(DD::new(1.0, perturb));
let apply = |u: &[P::Scalar]| -> Result<Vec<P::Scalar>, String> {
Ok(ap
.iter()
.map(|row| P::dot(row.iter().copied().zip(u.iter().copied())))
.collect())
};
let precond = |r: &[P::Scalar]| -> Result<Vec<P::Scalar>, String> {
let mut x = r.to_vec();
P::lu_solve(&m, &mut x);
Ok(x)
};
let opts = GcrOpts {
coef,
step_tol,
..Default::default()
};
let (x, info) = gcr::<P>(apply, precond, &b, &opts).unwrap();
let err = x
.iter()
.zip(&xs)
.map(|(&a, &b)| P::to_dd(a - b).hi.abs())
.fold(0.0, nan_max);
let scale = xs.iter().map(|&v| P::to_dd(v).hi.abs()).fold(0.0, nan_max);
(err / scale, info.products, info.converged)
}
#[test]
fn gcr_reaches_the_planted_solution() {
let (e, p, ok) = solve::<Double>(Coef::Full, 0.0, 1e-28);
println!("double-double, coefficients in P: error {e:.3e}, {p} products, converged {ok}");
assert!(ok && e <= 1e-29 && p <= 6);
let (e, p, ok) = solve::<Quad>(Coef::Full, 0.0, 1e-62);
println!("quad-double, coefficients in P: error {e:.3e}, {p} products, converged {ok}");
assert!(ok && e <= 1e-60 && p <= 10);
let (e, p, _) = solve::<Double>(Coef::F64, 0.0, 1e-28);
println!("double-double, f64 coefficients: error {e:.3e}, {p} products");
assert!(e <= 1e-12);
}
#[test]
fn gcr_control_inexact_products_miss() {
let (e, p, _) = solve::<Double>(Coef::Full, 1e-20, 1e-28);
println!("control, entry (3, 5) off by 1e-20: error {e:.3e} after {p} products");
assert!(e > 1e-25, "control did not fire");
}
fn dense_m(a: &[Vec<f64>], m: &[Vec<f64>], b: &[f64], nu: f64) -> (Vec<DD>, usize, bool) {
let mul = |a: &[Vec<f64>], u: &[DD]| -> Vec<DD> {
a.iter()
.map(|row| {
row.iter()
.zip(u)
.fold(DD::ZERO, |t, (&aij, &uj)| t + DD::from_f64(aij) * uj)
})
.collect()
};
let apply = |u: &[DD]| -> Result<Vec<DD>, String> { Ok(mul(a, u)) };
let precond = |r: &[DD]| -> Result<Vec<DD>, String> { Ok(mul(m, r)) };
let b: Vec<DD> = b.iter().map(|&v| DD::from_f64(v)).collect();
let opts = GcrOpts {
nu,
..Default::default()
};
let (x, info) = gcr::<Double>(apply, precond, &b, &opts).unwrap();
(x, info.products, info.converged)
}
fn dense(a: &[Vec<f64>], b: &[f64], nu: f64) -> (Vec<DD>, usize, bool) {
let id: Vec<Vec<f64>> = (0..b.len())
.map(|i| (0..b.len()).map(|j| (i == j) as u8 as f64).collect())
.collect();
dense_m(a, &id, b, nu)
}
fn shift(n: usize, sign: f64) -> Vec<Vec<f64>> {
(0..n)
.map(|i| {
(0..n)
.map(|j| match (i, j) {
(0, j) if j == n - 1 => sign,
(i, j) if i == j + 1 => 1.0,
_ => 0.0,
})
.collect()
})
.collect()
}
fn on_shift(n: usize, sign: f64, nu: f64) -> (bool, usize, bool) {
let mut b = vec![0.0; n];
b[0] = 1.0;
let (x, p, ok) = dense(&shift(n, sign), &b, nu);
let exact = (0..n).all(|i| x[i] == DD::from_f64(if i == n - 1 { sign } else { 0.0 }));
(exact, p, ok)
}
#[test]
fn gcr_does_not_break_down_where_gmres_stagnates() {
for (n, sign) in [(2, -1.0), (6, 1.0)] {
let (exact, p, ok) = on_shift(n, sign, 0.9);
println!("shift of size {n}: exact {exact}, {p} products, converged {ok}");
assert!(exact && p == n && ok);
let (exact, p, ok) = on_shift(n, sign, f64::INFINITY);
println!("control, residual directions only: exact {exact}, {p} products, converged {ok}");
assert!(!exact && !ok, "control did not fire");
}
}
#[test]
fn gcr_converges_on_an_exact_residual() {
let id = vec![vec![1.0, 0.0], vec![0.0, 1.0]];
let (x, p, ok) = dense(&id, &[1.0, 0.0], 0.9);
println!(
"A = I, b = e_0: x = ({}, {}), {p} products, converged {ok}",
x[0].hi, x[1].hi
);
assert!(x == [DD::ONE, DD::ZERO] && p == 1 && ok);
let (x, p, ok) = dense(&id, &[0.0, 0.0], 0.9);
println!("A = I, b = 0: {p} products, converged {ok}");
assert!(x == [DD::ZERO, DD::ZERO] && p == 0 && ok);
let (_, p, ok) = dense(&[vec![1.0, 0.0], vec![0.0, 0.0]], &[0.0, 1.0], 0.9);
println!("control, singular A, b = e_1: {p} products, converged {ok}");
assert!(!ok, "control did not fire");
}
#[test]
fn gcr_does_not_stop_on_a_zero_step_below_the_floor() {
let d = 2f64.powi(-110);
let a = vec![vec![1.0, 0.0, 0.0], vec![0.0, 0.0, -d], vec![0.0, d, 0.0]];
let m = vec![vec![1.0, 0.0, 0.0], vec![-d, 1.0, 0.0], vec![0.0, 0.0, 1.0]];
let want = [DD::ONE, DD::ZERO, -DD::ONE];
let (x, p, ok) = dense_m(&a, &m, &[1.0, d, 0.0], 0.9);
println!(
"weak block below the floor: x = ({}, {}, {}), {p} products, converged {ok}",
x[0].hi, x[1].hi, x[2].hi
);
assert!(x == want && p == 3 && ok);
let (x, p, ok) = dense_m(&a, &m, &[1.0, d, 0.0], f64::INFINITY);
println!(
"control, every iteration counts: x = ({}, {}, {}), {p} products, converged {ok}",
x[0].hi, x[1].hi, x[2].hi
);
assert!(x != want, "control did not fire");
}