# Dimension–Adaptive Tensor–Product Quadrature

@article{Gerstner2003DimensionAdaptiveTQ, title={Dimension–Adaptive Tensor–Product Quadrature}, author={Thomas Gerstner and Michael Griebel}, journal={Computing}, year={2003}, volume={71}, pages={65-87} }

We consider the numerical integration of multivariate functions defined over the unit hypercube. Here, we especially address the high–dimensional case, where in general the curse of dimension is encountered. Due to the concentration of measure phenomenon, such functions can often be well approximated by sums of lower–dimensional terms. The problem, however, is to find a good expansion given little knowledge of the integrand itself. The dimension–adaptive quadrature method which is developed and… Expand

#### Figures and Topics from this paper

#### 533 Citations

Adaptive Romberg-Quadrature for the Sparse Grid Combination Technique

- 2020

Many problems nowadays require approximations of high-dimensional integrals, because their analytical solutions cannot be provided. Among others, possible fields of application are Uncertainty… Expand

Numerical Comparison of Leja and Clenshaw-Curtis Dimension-Adaptive Collocation for Stochastic Parametric Electromagnetic Field Problems

- Computer Science
- ArXiv
- 2017

A dimension-adaptive, hierarchical interpolation scheme, based on nested univariate interpolation nodes, is employed in order to reduce the growth in complexity with the number of dimensions and to construct accurate polynomial surrogate models at a reduced computational cost compared to isotropic sparse grids. Expand

Efficient Numerical Methods for High-Dimensional Approximation Problems

- Mathematics
- 2019

Efficient Numerical Methods for High-Dimensional Approximation Problems Sören Wolfers In the field of uncertainty quantification, the effects of parameter uncertainties on scientific simulations may… Expand

Sparse Grids One-dimensional Multilevel Basis

- 2008

The sparse grid method is a general numerical discretization technique for multivariate problems. This approach, first introduced by the Russian mathematician Smolyak in 1963 [27], constructs a… Expand

Cubature formulas for function spaces with moderate smoothness

- Computer Science, Mathematics
- J. Complex.
- 2007

Lower bounds are proved showing that this method is optimal in dimension d=1 and almost optimal (up to logarithmic factors) in higher dimensions and the comparison with other cubature methods is performed. Expand

Approximate and integrate: Variance reduction in Monte Carlo integration via function approximation

- Mathematics
- 2018

Classical algorithms in numerical analysis for numerical integration (quadrature/cubature) follow the principle of approximate and integrate: the integrand is approximated by a simple function (e.g.… Expand

Local and Dimension Adaptive Sparse Grid Interpolation and Quadrature

- Mathematics, Computer Science
- ArXiv
- 2011

The proposed algorithm combines the strengths of the generalised sparse grid algorithm and hierarchical surplus-guided local adaptivity to obtain a high-order method which, given sufficient smoothness, performs significantly better than the piecewise-linear basis. Expand

Numerical Smoothing with Hierarchical Adaptive Sparse Grids and Quasi-Monte Carlo Methods for Efficient Option Pricing

- Economics, Computer Science
- ArXiv
- 2021

This study considers cases in which analytic smoothing cannot be performed, and introduces a novel numerical smoothing approach by combining a root finding algorithm with one-dimensional integration with respect to a single well-selected variable, proving that under appropriate conditions, the resulting function of the remaining variables is a highly smooth function. Expand

An Adaptive Sparse Grid Algorithm for Elliptic PDEs with Lognormal Diffusion Coefficient

- Mathematics
- 2015

In this work we build on the classical adaptive sparse grid algorithm (T. Gerstner and M. Griebel, Dimension-adaptive tensor-product quadrature), obtaining an enhanced version capable of using… Expand

Analysis of linear difference schemes in the sparse grid combination technique

- Mathematics
- 2007

Sparse grids are tailored to the approximation of smooth high-dimensional functions. On a $d$-dimensional tensor product space, the number of grid points is $N = \mathcal O(h^{-1} |\log h|^{d-1})$,… Expand

#### References

SHOWING 1-10 OF 61 REFERENCES

Numerical integration using sparse grids

- Mathematics, Computer Science
- Numerical Algorithms
- 2004

The usage of extended Gauss (Patterson) quadrature formulas as the one‐dimensional basis of the construction is suggested and their superiority in comparison to previously used sparse grid approaches based on the trapezoidal, Clenshaw–Curtis and Gauss rules is shown. Expand

Classification with sparse grids using simplicial basis functions

- Mathematics, Computer Science
- Intell. Data Anal.
- 2002

It turns out that the method scales linearly with the number of given data points and is well suited for data mining applications where the amount of data is very large, but where the dimension of the feature space is moderately high. Expand

Sparse grids

- Acta Numerica
- 2004

We present a survey of the fundamentals and the applications of sparse grids, with a focus on the solution of partial differential equations (PDEs). The sparse grid approach, introduced in Zenger… Expand

Optimized Tensor-Product Approximation Spaces

- Mathematics
- 2000

Abstract. This paper is concerned with the construction of optimized grids and approximation spaces for elliptic differential and integral equations. The main result is the analysis of the… Expand

A Note on the Complexity of Solving Poisson's Equation for Spaces of Bounded Mixed Derivatives

- Computer Science, Mathematics
- J. Complex.
- 1999

A strong tractability result of the order O(e−1) is given and this paper provides a practically usable hierarchical basis finite element method of this complexity O( e−1), i.e., without logarithmic terms growing exponentially in d, at least for the authors' sparse grid setting with its underlying smoothness requirements. Expand

Nonlinear approximation

- 1989

This is a survey of nonlinear approximation, especially that part of the subject which is important in numerical computation. Nonlinear approximation means that the approximants do not come from… Expand

Additive models in high dimensions

- Mathematics, Computer Science
- ArXiv
- 1999

A novel framework which includes the number of variables as an ingredient in the definition of the smoothness of the underlying functions is introduced, motivated by the effect of concentration of measure in high dimensional spaces and convergence of the additive decompositions is established. Expand

A New Algorithm for Multi-Dimensional Adaptive Numerical Quadrature

- Computer Science
- 1994

We present an algorithm for multi-dimensional quadrature that is adaptive both in the refinement of the subdomains and in the order. The method is based on an extrapolation technique using sparse… Expand

Weighted Tensor Product Algorithms for Linear Multivariate Problems

- Computer Science, Mathematics
- J. Complex.
- 1999

It is shown that these multivariate problems defined over weighted tensor product Hilbert spaces of functions f of d variables are sometimes tractable even with a worst-case assurance. Expand

Adaptive sparse grids

- Mathematics
- 2003

Sparse grids, as studied by Zenger and Griebel in the last 10 years have been very successful in the solution of partial differential equations, integral equations and classification problems.… Expand