# SPINTERP Piecewise multilinear hierarchical sparse grid interpolation

SPINTERP is a MATLAB library which can determine points defining a sparse grid in a multidimensional space, and given specific values at those points, can construct an interpolating function that can be evaluated anywhere.

The program can plot the interpolating function, perform optimization (seeking minima or maxima) and can integrate the function.

An early version of this library was documented and released as ACM TOMS Algorithm 847.

The sparse grid is constructed using Smolyak's construction. In fact, a nested series of grids is defined, each a refinement of the previous one, but chosen in such a way that the typical exponential growth in order does not occur. Moreover, because the grids are nested, the procedure produces a hierarchical series of piecewise linear interpolants. The nesting of these interpolants allows the estimation of the interpolation error.

The package includes several choices for the underlying one dimensional rule used to construct the sparse grids. The recommended rule is a Newton Cotes Closed rule, which produces grids of uniformly spaced points in [0,1], including the endpoints, of orders 1, 3, 5, 9, 17, 33, 65, and in general (2^I)+1. Note that the first rule is a special case (it doesn't include the endpoints, and the number of points in the rule is not equal to (2^0)+1!). Also note that the authors denote this rule as the "Clenshaw Curtis" or "CC" rule, although that name is more properly associated with the grid obtained by taking the cosine of the points given by the Newton Cotes Closed rule!

Another 1D rule is denoted by the authors as the "NB" or "no boundary" rule. This is simply a Newton Cotes Open rule which produces grids of uniformly spaced points in [0,1], omitting the endpoints, of orders 1, 3, 7, 15, 31, 63, and in general (2^(I+1))-1.

Another 1D rule is denoted by the authors as the "M" or "maximum norm" rule. This rule is the same as the CC rule, except that it starts with the rule of order 3. This seemingly minor difference forces this rule to use many more points than the other rules in the multidimensional case. The difference is evident in 2 dimensions, and quickly overwhelming even in dimensions as low as 4!

### Author:

Andreas Klimke,
Universitaet Stuttgart,
Stuttgart, Germany.

SPARSE GRID INTERPOLATION TOOLBOX - LICENSE

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

### Languages:

SPINTERP is available in a MATLAB version.

### Related Data and Programs:

RBF_INTERP, a MATLAB library which defines and evaluates radial basis interpolants to multidimensional data.

SMOLPACK, a C library which implements Novak and Ritter's method for estimating the integral of a function over a multidimensional hypercube using sparse grids.

SPARSE_GRID, a PYTHON library which contains classes and functions defining sparse grids, by Jochen Garcke.

SPARSE_GRID_HW, a MATLAB library which creates sparse grids based on Gauss-Legendre, Gauss-Hermite, Gauss-Patterson, or a nested variation of Gauss-Hermite rules, by Florian Heiss and Viktor Winschel.

SPARSE_INTERPOLANT a MATLAB library which can be used to define a sparse interpolant to a function f(x) of a multidimensional argument.

SPINTERP_EXAMPLES, a MATLAB library which demonstrates some simple uses of the spinterp program, which uses sparse grids for interpolation, optimization, and quadrature in higher dimensions.

SPQUAD, a MATLAB library which computes the points and weights of a sparse grid quadrature rule for a multidimensional integral, based on the Clenshaw-Curtis quadrature rule, by Greg von Winckel.

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

TOMS847, a MATLAB library which carries out piecewise multilinear hierarchical sparse grid interpolation; this library is commonly called SPINTERP (version 2.1); this is ACM TOMS Algorithm 847, by Andreas Klimke;

### Reference:

1. Volker Barthelmann, Erich Novak, Klaus Ritter,
High Dimensional Polynomial Interpolation on Sparse Grids,
Volume 12, Number 4, 2000, pages 273-288.
2. Alan Genz,
A Package for Testing Multiple Integration Subroutines,
in Numerical Integration: Recent Developments, Software and Applications,
edited by Patrick Keast, Graeme Fairweather,
Reidel, 1987, pages 337-340,
ISBN: 9027725144,
LC: QA299.3.N38
3. 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.
4. Andreas Klimke,
SPINTERP V2.1: Piecewise multilinear hierarchical sparse grid interpolation in MATLAB: Documentation.
5. Andreas Klimke,
SPINTERP V2.1: Examples: Reference Results..
6. Sergey Smolyak,
Quadrature and Interpolation Formulas for Tensor Products of Certain Classes of Functions,
Volume 4, 1963, pages 240-243.

### Source Code:

• plotgrid.m plots a sparse grid.
• plotindices.m visualizes the index sets of a 2d dimension-adaptive sparse grid.
• spcgsearch.m optimizes the sparse grid interpolant using the CG method.
• spcompsearch.m modified compass (coordinate) search algorithm.
• spdim.m computes the number of points in a sparse grid.
• spfminsearch.m optimization of sparse grids using FMINSEARCH.
• spget.m gets the sparse interpolation OPTIONS parameters.
• spgetseq.m computes the sequence of subgrids that form a sparse grid.
• spgrid.m computes the sparse grid point coordinates.
• spinit.m adds the sparse grid directories to the MATLAB path.
• spinterp.m evaluates a sparse grid interpolant.
• spmultistart.m implements the multiple random starting point optimization method for a sparse grid interpolant.
• spoptimget.m gets sparse grid optimization OPTIONS parameters.
• spoptimset.m create or alters the sparse grid optimization OPTIONS structure.
• sppurge.m purges sparse grid data.
• spquad.m computes the integral of the sparse grid interpolant.
• spset.m creates or alters the sparse interpolation OPTIONS structure.
• spsurfun.m evaluates the sparse grid interpolant function at a single point.
• spvals.m constructs a sparse grid interpolant.

### Other Directories

• doc contains the SPINTERP user manual as a PDF file.
• examples contains several M-files which can be used to demonstrate the features of SPINTERP.
• help contains HTML documentation for the toolbox, which can also be accessed inside the program by typing doc spinterptool.
• html contains PNG image files used in the documentation.
• private contains MATLAB functions needed by SPINTERP but of little direct interest to the user.

You can go up one level to the MATLAB source codes.

Last revised on 15 October 2009.