TOMS847 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. This library is commonly known as SPINTERP.
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!
SPINTERP is ACM TOMS Algorithm 847. A file containing the entire original source code is available through ACM: http://www.acm.org/pubs/calgo or NETLIB: http://www.netlib.org/toms/index.html.
Andreas Klimke,
Universitaet Stuttgart,
Stuttgart, Germany.
MULTILINEAR SPARSE GRID INTERPOLATION IN MATLAB
Copyright (c) 2003-2005,
Andreas Klimke,
Universitaet Stuttgart.
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.
CC_DISPLAY, a MATLAB library which can compute and display Clenshaw Curtis grids in two dimensions, as well as sparse grids formed from sums of Clenshaw Curtis grids.
CLENSHAW_CURTIS_RULE, a MATLAB library which can set up a Clenshaw Curtis quadrature grid in multiple dimensions.
QUADRATURE_RULES, a dataset directory which contains files that define quadrature rules; a number of examples of sparse grid quadrature rules are included.
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_CC, a dataset directory which contains files of abscissas of sparse grids based on a Clenshaw Curtis rule.
SPARSE_GRID_F2, a dataset directory which contains files of abscissas of sparse grids based on a Fejer Type 2 rule.
SPARSE_GRID_GP, a dataset directory which contains files of abscissas of sparse grids based on a Gauss Patterson rule.
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_GRID_NCC, a dataset directory which contains files of abscissas of sparse grids based on a Newton Cotes closed rule.
SPARSE_GRID_NCO, a dataset directory which contains files of abscissas of sparse grids based on a Newton Cotes open rule.
The following routines are of interest to the user:
These routines are probably of little direct interest to the user:
You can go up one level to the MATLAB source codes.
