Covering Pascal's Triangle on a Budget:
Accuracy, Precision, and Efficiency in Sparse Grids

A talk presented to the Mathematics Department,
Ajou University, Suwon, Korea, May 2009.

John Burkardt
Interdisciplinary Center for Applied Mathematics
Virginia Tech


We are now able to formulate interesting mathematical problems that
are naturally expressed in spaces of high dimension M, where M
may be 10, 20 or 100.  

Especially when the problem comes from a probabilistic setting,
or involves stochastic processes, we need to carry out integrals
in these high dimensional spaces.

For various reasons, we cannot rely on analytic methods, symbolic
algebra systems, or product rules, and Monte Carlo methods are unable
to produce accurate estimates.  In cases where the integrand function
is reasonably well behaved, it may be nonetheless possible to 
extract excellent estimates for integrals, using the method of
sparse grids.

We will introduce sparse grids by definition, construction
pictures, and application.  We will then explore the reasons
that a sparse grid can retrieve the information we want in 
cases where product rules "explode" and Monte Carlo rules 
"dawdle".