Sparse Grid Interpolation Toolbox Previous pageNext page

What is the Sparse Grid Interpolation Toolbox?

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. 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:

For additional information on the theoretical and algorithmic aspects of sparse grid interpolation, please refer to the references provided at the end of this chapter.