  Polynomial approximations of computationally intensive models are central to
uncertainty quantification. This paper describes an adaptive method for
non-intrusive pseudospectral approximation, based on Smolyak's algorithm with
generalized sparse grids. We rigorously analyze and extend the non-adaptive
method proposed in [6], and compare it to a common alternative approach for
using sparse grids to construct polynomial approximations, direct quadrature.
Analysis of direct quadrature shows that O(1) errors are an intrinsic property
of some configurations of the method, as a consequence of internal aliasing. We
provide precise conditions, based on the chosen polynomial basis and quadrature
rules, under which this aliasing error occurs. We then establish theoretical
results on the accuracy of Smolyak pseudospectral approximation, and show that
the Smolyak approximation avoids internal aliasing and makes far more effective
use of sparse function evaluations. These results are applicable to broad
choices of quadrature rule and generalized sparse grids. Exploiting this
flexibility, we introduce a greedy heuristic for adaptive refinement of the
pseudospectral approximation. We numerically demonstrate convergence of the
algorithm on the Genz test functions, and illustrate the accuracy and
efficiency of the adaptive approach on a realistic chemical kinetics problem.
