sparse_ir_sve/sve/residual.rs
1//! How well an SVE reproduces its kernel
2
3use nalgebra::DMatrix;
4
5use super::SVEResult;
6use crate::kernel::AbstractKernel;
7
8/// Position of the points next to the ends of a segment at which
9/// [`sve_residual`] compares, relative to the segment length. Strictly inside
10/// the segment, so that a kernel discontinuous at a knot is compared with the
11/// expansion on the same side of it.
12const END_OFFSET: f64 = 1.0 / 1048576.0;
13
14/// The points of each segment between `knots` at which [`sve_residual`]
15/// compares: next to both ends, where a polynomial interpolant departs most
16/// from the function it interpolates, and the midpoint
17fn residual_points(knots: &[f64]) -> Vec<f64> {
18 knots
19 .windows(2)
20 .flat_map(|w| {
21 let (a, b) = (w[0], w[1]);
22 let d = (b - a) * END_OFFSET;
23 [a + d, 0.5 * (a + b), b - d]
24 })
25 .collect()
26}
27
28/// The residual of the SVE `sve` of `kernel`, relative to the largest
29/// singular value: max |K(x, y) - Σ_l s_l u_l(x) v_l(y)| / s_0
30///
31/// The maximum is taken over the points next to both ends and at the
32/// midpoint of every segment of the singular functions, on both axes, where
33/// the expansion is evaluated in `f64`. The result measures the
34/// discretization of the kernel by the segments of its SVE hints (which
35/// [`compute_sve`](super::compute_sve) does not check) together with the
36/// truncation of the expansion, which contributes about the first singular
37/// value left out, below `epsilon`·s_0.
38///
39/// As a maximum over finitely many points, it is a lower bound of the
40/// maximum over the whole domain. For resolved and under-resolved kernels
41/// (exp(a x y) and the same times 1 + x/2, a ridge (1 + x/2) / (1 + 100 (x -
42/// y)²), √(1 + x) e^{xy}, and e^{-Λy(x+1)/2} / (1 + e^{-Λy}), on 1 to 32
43/// uniform segments per half axis), it was between 0.65 and 1.2 times the
44/// maximum over a 201 × 201 grid.
45///
46/// The evaluation in `f64` limits it from below: rounding x and y moves
47/// K(x, y) by about `f64::EPSILON` times |x ∂K/∂x| + |y ∂K/∂y|. For
48/// e^{-Λy(x+1)/2} / (1 + e^{-Λy}) with the segments of the IR basis, it is
49/// 8·10⁻¹⁴ at Λ = 10², 9·10⁻¹² at Λ = 10⁴ and 10⁻⁸ at Λ = 10⁶, for
50/// `epsilon` = 10⁻⁶ and 10⁻¹² alike, and does not decrease with more
51/// segments or Gauss points.
52///
53/// It evaluates the kernel in `f64` at 9 points per pair of segments, and
54/// the singular functions at these points; for the same kernel (Λ = 10² to
55/// 10⁶), that took 0.1 to 0.3 times as long as the SVE on 8 threads, and
56/// 0.06 to 0.12 times on one (it runs on the calling thread).
57pub fn sve_residual<K: AbstractKernel>(kernel: &K, sve: &SVEResult) -> f64 {
58 let s = sve.s();
59 let (u, v) = (sve.u().polys(), sve.v().polys());
60 let xs = residual_points(u[0].knots());
61 let ys = residual_points(v[0].knots());
62 // s_l u_l(x_i) and v_l(y_j), so that their product is the expansion
63 let mut us = DMatrix::<f64>::zeros(xs.len(), s.len());
64 let mut vs = DMatrix::<f64>::zeros(ys.len(), s.len());
65 for l in 0..s.len() {
66 for (i, ux) in u[l].evaluate_many(&xs).into_iter().enumerate() {
67 us[(i, l)] = s[l] * ux;
68 }
69 for (j, vy) in v[l].evaluate_many(&ys).into_iter().enumerate() {
70 vs[(j, l)] = vy;
71 }
72 }
73 let expansion = us * vs.transpose();
74 let mut residual: f64 = 0.0;
75 for (j, &y) in ys.iter().enumerate() {
76 for (i, &x) in xs.iter().enumerate() {
77 let k: f64 = kernel.compute(x, y);
78 let r = (k - expansion[(i, j)]).abs();
79 // NaN (from a kernel value that is not finite) must not be lost
80 // to max, which ignores it
81 if r.is_nan() {
82 return f64::NAN;
83 }
84 residual = residual.max(r);
85 }
86 }
87 residual / s[0]
88}