sparse_interp_nd


sparse_interp_nd, a C code which can be used to construct a sparse interpolant to a function f(x) of a multidimensional argument x.

The problem is defined as follows: for any point x in some M-dimensional product space X, such as the unit hypercube, we are able to provide the value f(x) for some function f(). We wish to determine a new function g(), (the interpolant) which will match the value of f() on some specified set of points {xi}. Presumably, we choose the number and location of the points {xi} to ensure that the interpolating function g() is a good fit to f().

There are standard techniques for producing a family of interpolants g(j)(), such that, as we increase the index j, the interpolating process will exactly match any function f() which happens to be a polynomial of limited degree. The usual techniques for doing this are derived from tensor product interpolants, whose expense grows exponentially with the spatial dimension.

For simplicity, we'll assume that the argument space X is the unit hypercube, and that we have a family of 1D interpolation rules g(j)(), where the index j is an indication of the precision of the interpolation rule. A typical tensor product interpolant G(J)() can then be thought of as constructed by the product

        G(J)(X) = g(j1)(x1) * g(j2)(x2) * ... * g(jm)(xm).
      
where, of course, J = (j1,j2,...jm) and X = (x1,x2,...,xm).

A procedure due to Smolyak, which is more typically applied to problems in quadrature, can also be used for the interpolation problem. The Smolyak interpolation rule of level L is defined by

        A(L,M) = sum ( L-M+1 <= |J| <= L ) C(|J|) * g(j1)(x1) * g(j2)(x2) * ... * g(jm)(xm).
      
Here |J| = j1+j2+...+jm, and, for each |J|, the sum must be taken over all possible vectors J with nonnegative integer entries that sum to |J|.

Thus, a naive implementation of a sparse interpolant would, for a given spatial dimension M, pick a level L, determine the (at most L+1) coefficients C(), construct every tensor product interpolant of total degree L or less, evaluate each interpolant at the point X, and combine these values with the appropriate weights C() to arrive at the sparse grid interpolant value at X.

Some improvements to this approach can be suggested. First, many of the coefficients C() may be zero, because the coefficient vector C for an M-dimensional sparse interpolant of level L will have at most M nonzero coefficients. Secondly, if the 1D interpolation family is chosen so that the interpolant points of successive members are nested, then it is possible to simplify the evaluation process greatly.

The code also requires access to the R8LIB library.

Licensing:

The computer code and data files described and made available on this web page are distributed under the MIT license

Languages:

sparse_interp_nd is available in a C version and a C++ version and a FORTRAN90 version and a MATLAB version.

Related Data and Programs:

LAGRANGE_INTERP_ND, a C code which defines and evaluates the Lagrange polynomial p(x) which interpolates a set of data depending on a multidimensional argument x that was evaluated on a product grid, so that p(x(i)) = z(i).

R8LIB, a C code which contains many utility routines using double precision real (R8) arithmetic.

RBF_INTERP_ND, a C code which defines and evaluates radial basis interpolants to multidimensional data.

SHEPARD_INTERP_ND, a C code which defines and evaluates Shepard interpolants to multidimensional data, based on inverse distance weighting.

sparse_interp_nd_test

TEST_INTERP_ND, a C code which defines test problems for interpolation of data z(x), depending on an M-dimensional argument.

Reference:

  1. Volker Barthelmann, Erich Novak, Klaus Ritter,
    High Dimensional Polynomial Interpolation on Sparse Grids,
    Advances in Computational Mathematics,
    Volume 12, Number 4, 2000, pages 273-288.
  2. Andreas Klimke, Barbara Wohlmuth,
    Algorithm 847: SPINTERP: Piecewise Multilinear Hierarchical Sparse Grid Interpolation in MATLAB,
    ACM Transactions on Mathematical Software,
    Volume 31, Number 4, December 2005, pages 561-579.
  3. Sergey Smolyak,
    Quadrature and Interpolation Formulas for Tensor Products of Certain Classes of Functions,
    Doklady Akademii Nauk SSSR,
    Volume 4, 1963, pages 240-243.

Source Code:


Last revised on 7 August 2019.