Sparse grid

Remarks

The full tensor grid $X^{q - d + 1} \times \cdots \times X^{q - d + 1}$ is the union of the products with every $i_j \le q - d + 1$; the sparse grid replaces this box condition on $\mathbf{i}$ by the simplex condition $i_1 + \cdots + i_d \le q$. Write $\ell = q - d + 1$ for the finest level in each direction. When $X^i$ has about $2^i$ points and $d$ is fixed, the sparse grid has $O(2^\ell \ell^{d-1})$ points, while the full grid $X^\ell \times \cdots \times X^\ell$ has about $2^{\ell d}$ points.

Example: take $I = [-1, 1]$, $X^1 = \set{0}$ and $X^2 = \set{-1, 0, 1}$, and $q = d + 1$. The allowed $\mathbf{i}$ are $(1, \dots, 1)$ and those with one entry $2$ and the others $1$. So $H(d + 1, d)$ consists of the origin and the $2d$ points $\pm e_j$, which makes $2d + 1$ points.

Non-example: the full grid $\set{-1, 0, 1}^d$ is not $H(d + 1, d)$ for $d \ge 2$, since it contains $(1, 1, 0, \dots, 0)$, which would need $\mathbf{i}$ with two entries equal to $2$ and so $i_1 + \cdots + i_d = d + 2 > q$.