MovingLeastSquares

Defined in header <ArborX_InterpMovingLeastSquares.hpp>

template<typename MemorySpace, typename FloatingCalculationType = double>
class Interpolation::MovingLeastSquares

Interpolate values from a set of source points to a set of target points using the moving least squares method.

For each target point, a polynomial is fitted by weighted least squares to the values at its nearest source points, and evaluated at the target point. The weights are given by a compactly supported radial basis function, see Compact radial basis functions. All the work that depends on the positions of the points only is done in the constructor. The interpolation itself, interpolate(), is a weighted sum of source values and can be repeated for as many sets of values as needed.

Template Parameters:
  • MemorySpace – A valid Kokkos memory space, in which the coefficients reside.

  • FloatingCalculationType – The floating-point type used internally to compute and store the coefficients.

template<typename ExecutionSpace, typename SourcePoints, typename TargetPoints, typename CRBFunc = CRBF::Wendland<0>, typename PolynomialDegree = PolynomialDegree<2>>
MovingLeastSquares(ExecutionSpace const &space, SourcePoints const &source_points, TargetPoints const &target_points, CRBFunc = {}, PolynomialDegree = {}, std::optional<int> num_neighbors = std::nullopt)

Compute the coefficients of the interpolation between the source points and the target points.

Parameters:
  • space – The execution space in which to run the algorithm.

  • source_points – The points at which the values to interpolate are known, accessed through AccessTraits.

  • target_points – The points at which to interpolate, accessed through AccessTraits.

  • CRBFunc – The compact radial basis function used to weight the source points, see Compact radial basis functions. The default is CRBF::Wendland<0>.

  • PolynomialDegree – The degree of the polynomial basis, see Polynomial degree. The default is a degree of 2.

  • num_neighbors – The number of source points, among the nearest neighbors of a target point, used to interpolate at that target point. It defaults to the size of the polynomial basis.

The following requirements must be satisfied.

  • MemorySpace must be accessible from ExecutionSpace.

  • A specialization of AccessTraits must match SourcePoints and TargetPoints as the template argument, and AccessTraits::get() must return a point.

  • The source points and the target points must have the same dimension and be accessible from ExecutionSpace.

  • num_neighbors must be positive and at most the number of source points.

The interpolation is exact, up to machine precision, for any function in the span of the polynomial basis, provided the Vandermonde matrix of the basis evaluated at the neighbors of the target point has full rank. Otherwise, the higher-order terms are dropped from the polynomial basis for that target point, which gives a better interpolation of lower-order polynomials.

template<typename ExecutionSpace, typename SourceValues, typename ApproxValues>
void interpolate(ExecutionSpace const &space, SourceValues const &source_values, ApproxValues &approx_values) const

Compute the interpolated values at the target points from the values at the source points, using the coefficients computed by the constructor. It may be called any number of times.

Parameters:
  • space – The execution space in which to run the algorithm.

  • source_values – The values at the source points.

  • approx_values – The view in which the interpolated values at the target points are stored.

The following requirements must be satisfied.

  • MemorySpace must be accessible from ExecutionSpace.

  • SourceValues and ApproxValues must be one-dimensional Kokkos views accessible from ExecutionSpace, and the value type of ApproxValues must not be const.

  • source_values must have one entry per source point, in the order of the source_points passed to the constructor.

  • approx_values must have one entry per target point, in the order of the target_points passed to the constructor.

Compact radial basis functions

A compact radial basis function (CRBF) is a function of the distance to the target point, rescaled so that the farthest neighbor is slightly inside the support of the function, which is the unit ball. Source points get a weight that decreases to zero as they get farther away. The CRBFunc argument of the constructor is one of the following types, each parameterized by a smoothness-related integer N.

template<std::size_t N>
struct Interpolation::CRBF::Wendland

The Wendland functions [1] are available for N in 0, 2, 4, and 6. For instance, Wendland<0> is (1 - x)^2 and Wendland<2> is (1 - x)^4 (4x + 1), for x in [0, 1].

template<std::size_t N>
struct Interpolation::CRBF::Wu

The Wu functions [2] are available for N in 2 and 4. For instance, Wu<2> is (1 - x)^4 (3x^3 + 12x^2 + 16x + 4), for x in [0, 1].

template<std::size_t N>
struct Interpolation::CRBF::Buhmann

The Buhmann functions [3] are available for N in 2, 3, and 4.

Each of these has a static member function that evaluates the function. Its argument is clamped to [0, 1] after taking its absolute value, and DIM is the dimension of the points, as the functions depend on it.

template<std::size_t DIM, typename T>
static constexpr T Interpolation::CRBF::Wendland::evaluate(T const x)

Evaluate the function.

Polynomial degree

template<std::size_t Degree>
using Interpolation::PolynomialDegree = std::integral_constant<std::size_t, Degree>

The degree of the polynomial basis, which contains all the monomials of the coordinates of the points up to that degree. For points of dimension d, it has \(\binom{d + Degree}{d}\) terms, e.g., 6 in 2D and 10 in 3D for a degree of 2.

Use it as, e.g., Interpolation::PolynomialDegree<1>{}.

Example

The example below interpolates \(\cos(x + y / 4)\) from a 3x3 grid of points to three points that are not on the grid. The default compact radial basis function and polynomial degree are used.

#include <ArborX.hpp>
#include <ArborX_InterpMovingLeastSquares.hpp>

#include <Kokkos_Core.hpp>

#include <iostream>

using Point = ArborX::Point<2, double>;

KOKKOS_FUNCTION double functionToApproximate(Point const &p)
{
  return Kokkos::cos(p[0] + p[1] / 4);
}

int main(int argc, char *argv[])
{
  Kokkos::ScopeGuard guard(argc, argv);

  using ExecutionSpace = Kokkos::DefaultExecutionSpace;
  using MemorySpace = typename ExecutionSpace::memory_space;
  ExecutionSpace space{};

  // Source space is a 3x3 grid
  // Target space is 3 off-grid points
  //
  //  ^
  //  |
  //  S     S     S
  //  |
  //  |   T
  //  S     S  T  S
  //  |
  //  | T
  // -S-----S-----S->
  //  |

  int const num_sources = 9;
  int const num_targets = 3;

  // Set up points
  Kokkos::View<Point *, MemorySpace> src_points("Example::src_points",
                                                num_sources);
  Kokkos::View<Point *, MemorySpace> tgt_points("Example::tgt_points",
                                                num_targets);
  Kokkos::parallel_for(
      "Example::make_points", Kokkos::RangePolicy(space, 0, 1),
      KOKKOS_LAMBDA(int const) {
        src_points(0) = {0., 0.};
        src_points(1) = {1., 0.};
        src_points(2) = {2., 0.};
        src_points(3) = {0., 1.};
        src_points(4) = {1., 1.};
        src_points(5) = {2., 1.};
        src_points(6) = {0., 2.};
        src_points(7) = {1., 2.};
        src_points(8) = {2., 2.};
        tgt_points(0) = {4. / 6., 4. / 3.};
        tgt_points(1) = {9. / 6., 3. / 3.};
        tgt_points(2) = {2. / 6., 1. / 3.};
      });

  // Set up values
  Kokkos::View<double *, MemorySpace> src_values("Example::src_values",
                                                 num_sources);
  Kokkos::View<double *, MemorySpace> app_values("Example::app_values",
                                                 num_targets);
  Kokkos::View<double *, MemorySpace> ref_values("Example::ref_values",
                                                 num_targets);
  Kokkos::parallel_for(
      "Example::make_values", Kokkos::RangePolicy(space, 0, num_sources),
      KOKKOS_LAMBDA(int const i) {
        src_values(i) = functionToApproximate(src_points(i));
        if (i < num_targets)
          ref_values(i) = functionToApproximate(tgt_points(i));
      });

  // Build the moving least squares coefficients
  ArborX::Interpolation::MovingLeastSquares<MemorySpace> mls(space, src_points,
                                                             tgt_points);

  // Interpolate
  mls.interpolate(space, src_values, app_values);

  // Show results
  auto app_values_host =
      Kokkos::create_mirror_view_and_copy(Kokkos::HostSpace{}, app_values);
  auto ref_values_host =
      Kokkos::create_mirror_view_and_copy(Kokkos::HostSpace{}, ref_values);
  auto diff = [=](int const i) {
    return Kokkos::abs(app_values_host(i) - ref_values_host(i));
  };

  std::cout << "Approximated values: " << app_values_host(0) << ' '
            << app_values_host(1) << ' ' << app_values_host(2) << '\n';
  std::cout << "Real values        : " << ref_values_host(0) << ' '
            << ref_values_host(1) << ' ' << ref_values_host(2) << '\n';
  std::cout << "Differences        : " << diff(0) << ' ' << diff(1) << ' '
            << diff(2) << '\n';

  return 0;
}

It prints

Approximated values: 0.503076 -0.156426 0.87675
Real values        : 0.540302 -0.178246 0.914443
Differences        : 0.0372265 0.0218204 0.0376936

References