## Description

Multivariate integrals arise in many application fields, such as statistics, the valuation of financial derivatives, the discretization of partial differential and integral equations or the numerical computation of path integrals. Conventional algorithms for the numerical computation of such integrals are often limited by the curse of dimension meaning that the computing cost grows exponentially with the dimension of the problem.

However, for special function classes, such as spaces of functions which have bounded mixed derivatives, Smolyak's construction (also known as sparse grid method) can overcome this curse of dimension to a certain extent. In this approach, multivariate quadrature formulas are constructed using combinations of tensor products of suited one-dimensional formulas. In this way, the number of function evaluations and the numerical accuracy get independent of the dimension of the problem up to logarithmic factors. Below you see the quadrature abscissas from a Monte Carlo and a Quasi-Monte Carlo method, a lattice rule, and a sparse grid, all of which can break the curse of dimension.

Sparse grid quadrature formulas come in various types depending on a one-dimensional basis integration routine. In the next picture we see sparse grids based on the trapezoidal, the Clenshaw-Curtis, Patterson and Gauss-Legendre rules. Theoretical and experimental computations have shown that Patterson formulas are sort of optimal for Smolyak's construction.

The scope of this project is to apply sparse grid quadrature formulas to various problems from finance. These problems typically require the computation of expecations, which are integrals whose dimension is infinite for continuous processes and finite but high for discrete processes. The Brownian bridge construction helps to reduce the effective dimension of these integrals. Below, you see a sample random process, and corresponding discretizations using a random walk and the Brownian bridge construction.

Below, you see the location of the integration points for two-step geometric Asian option. Here, in order to avoid the discontinuity in the derivative of the (transformed) payoff function, the integration domain was transformed to the smooth nonzero part of the payoff function.

## References

• T. Bonk, A new algorithm for multi-dimensional adaptive numerical quadrature, in Adaptive Methods - Algorithms, Theory and Applications, W. Hackbusch, G. Wittum (eds.), pp. 54-68, Vieweg, Braunschweig, 1994.
• T. Gerstner, M. Griebel, Numerical integration using sparse grids, Numerical Algorithms 18:209-232, 1998.
• T. Gerstner, M. Griebel, Dimension-adaptive tensor-product quadrature, Computing (special issue on sparse grids), 2002, submitted.
• T. Gerstner, M. Griebel, S. Wahl, Option pricing using sparse grids, 2001, available on request.
• E. Novak, K. Ritter, High dimensional integration of smooth functions over cubes, Numerische Mathematik 75, pp. 79-97, 1996.
• S.A. Smolyak, Quadrature and interpolation formulas for tensor products of certain classes of functions, Dokl. Akad. Nauk SSSR 4, pp. 240-243, 1963.
• The Sparse Grid Bibliography.

Thomas Gerstner