# Sparse grid interpolation and engineering applications

#### Introduction

The interpolation problem considered with sparse grid 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. The asymptotic error decay of full grid interpolation is preserved up to a logarithmic factor with increasing grid resolution. 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.

#### Sparse Grid Interpolation Toolbox for Matlab

A Matlab toolbox has been developed that 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:
• Enable vectorized processing. Speed up the construction of the interpolant for functions that allow for vectorized evaluation.
• Create multiple interpolants at once for functions with multiple output arguments.
• Choose from three different grid types for piecewise linear interpolation. Depending on your objective function, a certain grid type may perform better than the others.
• If very high accuracies are required, you may use the Chebyshev-Gauss-Lobatto sparse grid, which employs polynomial basis functions.
• Compute gradients along with the interpolated values at just a small additional cost.
• Integrate the interpolant.
• Perform a search for minima and maxima using several efficient algorithms.
• Use a dimension-adaptive algorithm to automatically detect separability, and to take the importance of the dimensions into account when constructing the interpolant. This is especially useful in case of very high-dimensional problems when a regular sparse grid refinement leads to too many support nodes.
• The Sparse Grid Interpolation toolbox is designed to easily integrate with your models in Matlab as well as external models.

#### Examples for Dimension-Adaptive Sparse Grid Interpolation

With piecewise linear basis functions, f(x,y) = exp(-5x2) + exp(-5y2):

With polynomial basis functions, Branin's function:

#### Publications

Publications of the group on sparse grids -including many applications to engineering problems- are listed below.

Hans-Joachim Bungartz, Ionut-Gabriel Farcas, Jonas Latz, Tobias Neckel, Elisabeth Ullmann Multilevel Adaptive Sparse Leja Approximations for Bayesian Inverse Problems submitted 2019 Article in Journal Abstract
Bibtex
Corinna Hager, Stefan Hüeber, Barbara Wohlmuth Numerical techniques for the valuation of basket options and its Greeks J. Comput. Fin. 13(4), 1-31 2010 Article in Journal Abstract
Bibtex
Andreas Klimke, Christopher J. Pye Sparse grid meta-models for model updating Proceedings of the IMAC XXVII Conference, Orlando, Fl 2009 Article in Conference Proceedings Abstract
Bibtex
Andreas Klimke Sparse grid surrogate functions for nonlinear systems with parameter uncertainty Proceedings of the 1st International Conference on Uncertainty in Structural Dynamics, 159-168 2007 Article in Conference Proceedings Abstract
PDF
Bibtex
Andreas Klimke Uncertainty Modeling using Fuzzy Arithmetic and Sparse Grids PhD thesis, Universität Stuttgart 2006 PhD Thesis Abstract
PDF
Bibtex
Andreas Klimke Sparse Grid Interpolation Toolbox User's Guide IANS Documentation 2006/001 2006 Technical Manual Abstract
PDF
Bibtex
Andreas Klimke, Barbara Wohlmuth Constructing dimension-adaptive sparse grid interpolants using parallel function evaluations Parallel Process. Lett. 16, 407-418 2006 Article in Journal Abstract
Bibtex
Andreas Klimke Construction of Hierarchical Polynomial Sparse Grid Interpolants using the Fast Discrete Cosine Transform IANS Preprint 2006/007 2006 Preprint Abstract
Bibtex
Andreas Klimke, Ronaldo Nunes, Barbara Wohlmuth Fuzzy arithmetic based on dimension-adaptive sparse grids: a case study of a large-scale finite element model under uncertain parameters Internat. J. Uncertain. Fuzziness Knowledge-Based Systems 14, 561-577 2006 Article in Journal Abstract
Bibtex
Andreas Klimke, Barbara Wohlmuth Computing expensive multivariate functions of fuzzy numbers using sparse grids Fuzzy Sets and Systems 154, 432-453 2005 Article in Journal Abstract
Bibtex
Andreas Klimke, Barbara Wohlmuth Piecewise multilinear hierarchical sparse grid interpolation in Matlab ACM Trans. Math. Software. 31, 561-579 2005 Article in Journal Abstract