Accuracy, Precision, and Efficiency in Sparse Grids

A talk presented to the Computer Science Research Institute (CSRI),
Sandia National Laboratory, July 2009.

John Burkardt
Interdisciplinary Center for Applied Mathematics
Virginia Tech


In the quest for accuracy, modern computational science 
has been driven into abstract spaces of very high dimension.
These spaces can represent the problem very well, but 
extracting a numerical answer requires the formidable
task of approximating an integral in a high dimensional space.

The Monte Carlo method is always useful for these kinds
of approximations, no matter what the integrand function.
The robustness of this method comes at a cost of a limited
convergence rate.

Especially when a problem comes from a probabilistic or stochastic
setting, the integrand function is likely to be very smooth.
In this case, sparse grid rules can be formulated which are
competitive with the Monte Carlo approach.

We will introduce sparse grids by definition, construction,
pictures, and application.  We will then explore how the 
precision of a sparse grid, achieved efficiently, results
in an accurate integral estimate at a reasonable cost.