Andreas Klimke
Abstract
To recover or approximate smooth multivariate functions, sparse grids are superior to full grids due to a significant reduction of the required support nodes. The order of the convergence rate in the maximum norm is preserved up to a logarithmic factor. We describe three possible piecewise multilinear hierarchical interpolation schemes in detail and conduct a numerical comparison. Furthermore, we document the features of our sparse grid interpolation software package spinterp for MATLAB.
Supplemental Material
Available for Download
Software for "Spinterp: piecewise multilinear hierarchical sparse grid interpolation in MATLAB"
- Barthelmann, V., Novak, E., and Ritter, K. 2000. High dimensional polynomial interpolation on sparse grids. Adv. Comput. Math. 12, 4, 273--288.Google Scholar
- Bungartz, H.-J. 1992. Dünne Gitter und deren Anwendung bei der adaptiven Lösung der dreidimensionalen Poissongleichung. Ph.D. dissertation. Technische Universität München, Munich, Germany.Google Scholar
- Bungartz, H.-J. 1998. Finite Elements of Higher Order on Sparse Grids. Shaker Verlag, Aachen, Germany.Google Scholar
- Bungartz, H.-J. and Griebel, M. 2004. Sparse grids. Acta Numerica 13, 147--269.Google Scholar
- Clenshaw, C. W. and Curtis, A. R. 1960. A method for numerical integration on an automatic computer. Numer. Math. 2, 197--205.Google Scholar
- Genz, A. C. 1987. A package for testing multiple integration subroutines. In Numerical Integration, P. Keast and G. Fairweather, Eds. Kluwer, Dordrecht, The Netherlands, 337--340.Google Scholar
- Klimke, A. 2006. Uncertainty modeling using sparse grids. PhD dissertation. Universität Stuttgard, Germany.Google Scholar
- Klimke, A., Willner, K., and Wohlmuth, B. 2004. Uncertainty modeling using fuzzy arithmetic based on sparse grids: Applications to dynamic systems. Int. J. Uncertaint. Fuzz. Knowl.-Based Syst. 12, 6, 745--759.Google Scholar
- Klimke, A. and Wohlmuth, B. 2005. Computing expensive multivariate functions of fuzzy numbers using sparse grids. Fuzz. Sets Syst. 154, 3, 432--453. Google Scholar
- Novak, E. and Ritter, K. 1996. High-dimensional integration of smooth functions over cubes. Numer. Math. 75, 1, 79--97.Google Scholar
- Schreiber, A. 2000. Smolyak's method for multivariate interpolation. Ph.D. dissertation. Georg-August-Universität Göttingen, Göttingen, Germany.Google Scholar
- Shampine, L. F. and Reichelt, M. W. 1997. The MATLAB ODE suite. SIAM J. Sci. Comput. 18, 1, 1--22. Google Scholar
- Smolyak, S. A. 1963. Quadrature and interpolation formulas for tensor products of certain classes of functions. Soviet Math. Dokl. 4, 240--243.Google Scholar
- Sprengel, F. 1997. Interpolation and wavelets on sparse Gauss-Chebyshev grids. In Multivariate Approximation, W. Haussmann et al., Eds. Mathematical Research, vol. 101. Akademie Verlag, Berlin, Germany, 269--286.Google Scholar
- Sprengel, F. 1998. Periodic interpolation and wavelets on sparse grids. Numer. Algorith. 17, 1--2, 147--169.Google Scholar
Index Terms
- Algorithm 847: Spinterp: piecewise multilinear hierarchical sparse grid interpolation in MATLAB
Recommendations
Shape-preserving, multiscale interpolation by bi- and multivariate cubic L1 splines
We introduce a class of bi- and multivariate cubic L"1 interpolating splines, the coefficients of which are calculated by minimizing the sum of the L"1 norms of second derivatives. The focus is mainly on bivariate cubic L"1 splines for C^1 interpolation ...
Sparse interpolation of multivariate rational functions
Consider the black box interpolation of a -sparse, n-variate rational function f, where is the maximum number of terms in either numerator or denominator. When numerator and denominator are at most of degree d, then the number of possible terms in f is ...
An algorithm for multivariate function estimation based on hierarchically refined sparse grids
An adaptive function estimation approach is presented to recover an unknown, multivariate functional relation from noisy data. Using a sparse grid combination approach, both discretization and Tikhonov regularization need to be selected appropriately to ...
Reviews
Kai Diethelm
In many applications, there is a need for accurate interpolation and approximation of multivariate functions. The most obvious approach, a tensor product of univariate methods, suffers from a very high complexity, and thus extremely long runtimes, especially if the number of dimensions is large. A classical paper of Smolyak [1] introduces a concept that is now commonly known as sparse grids, which allows the complexity to be reduced by a large amount with only a negligible loss of accuracy. It is particularly efficient when the underlying univariate method is of a hierarchical type, that is, if its nodes on a certain level form a subset of its nodes on higher levels. This paper presents a special case of this algorithm, based on piecewise linear one-dimensional interpolation methods. Three choices of interpolation nodes are considered and compared in a detailed way. A complete description of a MATLAB implementation is given, together with illustrative results for a selection of typical numerical examples. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments