  Multivariate global polynomial approximations - such as polynomial chaos or
stochastic collocation methods - are now in widespread use for sensitivity
analysis and uncertainty quantification. The pseudospectral variety of these
methods uses a numerical integration rule to approximate the Fourier-type
coefficients of a truncated expansion in orthogonal polynomials. For problems
in more than two or three dimensions, a sparse grid numerical integration rule
offers accuracy with a smaller node set compared to tensor product
approximation. However, when using a sparse rule to approximately integrate
these coefficients, one often finds unacceptable errors in the coefficients
associated with higher degree polynomials.
  By reexamining Smolyak's algorithm and exploiting the connections between
interpolation and projection in tensor product spaces, we construct a sparse
pseudospectral approximation method that accurately reproduces the coefficients
of basis functions that naturally correspond to the sparse grid integration
rule. The compelling numerical results show that this is the proper way to use
sparse grid integration rules for pseudospectral approximation.
