  In this work, we develop a novel efficient quadrature and sparse grid based
polynomial interpolation method to price American options with multiple
underlying assets. The approach is based on first formulating the pricing of
American options using dynamic programming, and then employing static sparse
grids to interpolate the continuation value function at each time step. To
achieve high efficiency, we first transform the domain from $\mathbb{R}^d$ to
$(-1,1)^d$ via a scaled tanh map, and then remove the boundary singularity of
the resulting multivariate function over $(-1,1)^d$ by a bubble function and
simultaneously, to significantly reduce the number of interpolation points. We
rigorously establish that with a proper choice of the bubble function, the
resulting function has bounded mixed derivatives up to a certain order, which
provides theoretical underpinnings for the use of sparse grids. Numerical
experiments for American arithmetic and geometric basket put options with the
number of underlying assets up to 16 are presented to validate the
effectiveness of the approach.
