The interpolation problem considered with sparse grid [1] interpolation is an optimal recovery problem (i.e. the selection of points such that a smooth multivariate function can be approximated with a suitable interpolation formula). Depending on the characteristics of the function to interpolate (degree of smoothness, periodicity), various interpolation techniques based on sparse grids exist. All of them employ Smolyak's construction, which forms the basis of all sparse grid methods. With Smolyak's famous method, well-known univariate interpolation formulas are extended to the multivariate case by using tensor products in a special way. As a result, one obtains a powerful interpolation method that requires significantly fewer support nodes than conventional interpolation on a full grid. The points comprising the multidimensional sparse grid are selected in a predefined fashion. The difference in the number of required points can be several orders of magnitude with increasing problem dimension. The most important property of the method constitutes the fact that the asymptotic error decay of full grid interpolation with increasing grid resolution is preserved up to a logarithmic factor. An additional benefit of the method is its hierarchical structure, which can be used to obtain an estimate of the current approximation error. Thus, one can easily develop an interpolation algorithm that aborts automatically when a desired accuracy is reached.

Major Features

This Matlab toolbox includes hierarchical sparse grid interpolation algorithms based on both piecewise multilinear and polynomial basis functions. Special emphasis is placed on an efficient implementation that performs well even for very large dimensions d > 10.

There are many ways to customize the behavior of the interpolation routines. Furthermore, additional tasks involving the interpolants can be performed, such as computing derivatives or performing an optimization or integration. The following list gives an overview of the options that are available:

Selected References

[1]  H.-J. Bungartz and M. Griebel. Sparse grids. Acta Numerica 13:147-269, 2004.
[2] A. Klimke and B. Wohlmuth. Algorithm 847: spinterp: Piecewise multilinear hierarchical sparse grid interpolation in MATLAB. ACM Transactions on Mathematical Software, 31(4), 2005.
[3] A. Klimke. Uncertainty Modeling using Fuzzy Arithmetic and Sparse Grids, PhD Thesis, Universität Stuttgart, Shaker Verlag, Aachen, 2006.
[4] V. Barthelmann, E. Novak, and K. Ritter. High dimensional polynomial interpolation on sparse grids. Adv. Comput. Math., 12(4):273-288, 2000.
[5] H.-J. Bungartz. Finite Elements of Higher Order on Sparse Grids. Shaker Verlag, Aachen, 1998.
[6] A. Klimke. Efficient construction of hierarchical polynomial sparse grid interpolants using the fast discrete cosine transform. Technical Report IANS Preprint 2006/007, Universität Stuttgart, 2006.
[7] M. Hegland. Adaptive sparse grids. In K. Burrage and R. B. Sidje, editors, Proceedings of the 2001 International conference on Computational Techniques and Applications, University of Queensland, volume 44 of ANZIAM Journal, pages C335-C353, 2003. 59
[8] T. Gerstner and M. Griebel. Dimension-adaptive tensor-product quadrature. Computing, 71(1):65-87, 2003.
[9] T.N.L. Patterson. The Optimum Addition of Points to Quadrature Formulae. Mathematics of Computation, 22(104):847-856+s21-s31, 1968.
[10] T. Gerstner and M. Griebel. Numerical Integration using Sparse Grids Numerical Algorithms, 18(3-4):209-232, 1998.