---
tag: 4FBC8218YE
kind: definition
name: Sparse grid
msc: [65D32, 41A63, 65D05]
defines: 84BR7X6HET
uses: [ADSVMCY77A]
sources:
  - url: https://en.wikipedia.org/wiki/Sparse_grid
---

## Definition

Let $d \ge 1$ and let $X^1 \subseteq X^2 \subseteq X^3 \subseteq \cdots$ be a nested sequence of finite subsets of an interval $I$.
For an integer $q \ge d$, the *sparse grid* of level $q$ in dimension $d$ is the set
$$H(q, d) = \bigcup_{\substack{\mathbf{i} \in \N^d,\ i_1, \dots, i_d \ge 1 \\ i_1 + \cdots + i_d \le q}} X^{i_1} \times X^{i_2} \times \cdots \times X^{i_d} \subseteq I^d.$$
Let $U^i$ be a [[quadrature rule|ADSVMCY77A]] on $I$ with nodes $X^i$, let $U^0 = 0$, and let $\Delta^i = U^i - U^{i-1}$.
The Smolyak rule is
$$A(q, d) = \sum_{i_1 + \cdots + i_d \le q} \Delta^{i_1} \otimes \cdots \otimes \Delta^{i_d}.$$
It is a rule on $I^d$ whose nodes lie in $H(q, d)$.

## 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$.