Sparse grid

Summary

A sparse grid is a set of points in a cube in $\R^d$ built by Smolyak's construction from one-dimensional rules. It keeps only those products of one-dimensional levels whose total level is small, instead of the full tensor grid. For functions with bounded mixed derivatives, sparse grids give nearly the accuracy of full grids with far fewer points. They are used for integration and interpolation in moderately high dimensions, where full grids suffer from the curse of dimensionality.