Sparse grids vs. random points for high-dimensional polynomial approximation

Jakob Eggl, Elias Mindlberger, Mario Ullrich

We study polynomial approximation on a $d$-cube, where $d$ is large, and compare interpolation on sparse grids, aka Smolyak's algorithm (SA), with a simple least squares method bas…