SPARSE GRIDS - Extracting Information in High Dimensions

John Burkardt
Interdisciplinary Center for Applied Mathematics
Virginia Tech

The relentless development of mathematical techniques
and computing power has made it possible to pose integral
problems in abstract spaces of very high dimension.  
Approximate methods that work well in lower dimensions
can become impractical, unreliable, or inefficient as the
dimension is increased.

Product grids, in particular, fail spectactularly in
high dimensions, and yet these grids have many attractive
properties.  They allow us to specify particular rules
in each dimension, they can be constructed to take advantage
of nesting, and they can be made to have desirable
exactness properties.

Smolyak's sparse grid construction provides a way to retain
the desirable properties of a product grid, while avoiding
the catastrophic explosion in the number of points needed to
define a quadrature rule.

We will examine the algorithm that is used to develop a sparse
grid.  We will discuss the kinds of problems for which a Smolyak 
sparse grid can be expected to compete or outperform the Monte Carlo
method and its relatives.  We will discuss some software that
makes it possible to use a sparse grid as though it were just
another quadrature rule.