Skip to main content

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}