Sparse-Grid Methods
Sparse grids beat the curse of dimensionality by combining low-order tensor grids, giving accurate integration and interpolation in moderate dimension.
The dimensionality problem
A full tensor-product grid with m points per dimension needs m^d points in d dimensions, infeasible beyond a few dimensions. Sparse grids, based on Smolyak's construction, drop the high-order cross terms that contribute least, retaining accuracy for smooth functions with far fewer points.
Smolyak construction
Smolyak's rule combines tensor products of one-dimensional rules whose total level is bounded, weighting them so that lower-order interactions are captured exactly. The point count grows roughly polynomially in dimension for a fixed accuracy, rather than exponentially, which is the decisive advantage.
Nested rules
- Nested 1-D rules (Clenshaw-Curtis, Gauss-Patterson) let coarser grids be reused as levels increase
- Nesting minimizes total function evaluations across refinement
- Delayed and adaptive variants add points only where the response varies
Adaptivity
Dimension-adaptive and locally-adaptive sparse grids concentrate points on the inputs and regions that matter, guided by error indicators. This handles anisotropy, where a few inputs dominate, and mild non-smoothness far better than an isotropic grid. Adaptivity is what makes sparse grids practical for real engineering models.
Limits
Sparse grids still assume enough smoothness; they lose their advantage for discontinuous responses and eventually succumb to dimensionality above roughly ten to twenty inputs without adaptivity or reduction. Pairing sparse grids with active-subspace or screening-based dimension reduction extends their reach, and interpolation residuals should be checked to confirm the smoothness assumption holds.