# Finite Differences on Sparse Grids for Continuous-Time Heterogeneous Agent Models
## 3 Sparse Grids  
Sparse grids were introduced in [28] and date back to [29]. We give only a short introduction here. See [30; 31; 32] for details and approximation properties. To construct sparse grids, one uses a tensor product construction to obtain a multi-dimensional basis on the \(d\)-dimensional unit cube \(\bar{\Omega}:=[0,1]^{d}\) from the one-dimensional hierarchical basis. We use the multi-index \(\mathbf{I}=(l_{1},\ldots,l_{d})\in\mathbb{N}^{d}\) to denote the level. We then consider the set of \(d\)-dimensional rectangular grids \(\Omega_{\mathbf{I}}\) with mesh size  
\[\mathbf{h_{i}}:=(h_{l_{1}},\ldots,h_{l_{d}}):=2^{-1}.\]  
With each individual grid point \(x_{\mathbf{i},\mathbf{i}}\), where \(\mathbf{i}\) indicates its spatial position, we associate a piecewise d-linear nodal basis function,  
\[\Phi_{\mathbf{i},\mathbf{i}}(x):=\prod_{j=1}^{d}\phi_{l_{j},i_{j}}(x_{j}),\]  
which is the product of the one-dimensional basis functions and has a support of size \(2\mathbf{h_{i}}\). The one-dimensional \(\phi_{l_{j},i_{j}}(x_{j})\) are the well-known hat functions. Using these basis functions, we can define the \(d\)-dimensional nodal function spaces  
\[V_{\mathbf{i}}:=\text{span}\{\Phi_{\mathbf{i},\mathbf{i}}:\mathbf{1}\leq \mathbf{i}\leq 2^{\mathbf{i}}-\mathbf{1}\}\]  
which are zero on the boundary \(\partial\Omega\) and consist of piecewise \(d\)-linear functions, and the \(d\)-dimensional hierarchical increment spaces  
\[W_{\mathbf{i}}:=\text{span}\{\Phi_{\mathbf{i},\mathbf{i}}:\mathbf{i}\in \mathbb{N}^{d}:\mathbf{1}\leq\mathbf{i}\leq 2^{\mathbf{i}}-\mathbf{1},\ i_{j} \text{ odd }\forall\mathbf{1}\leq j\leq d\ \}.\]  
Let us define the _full grid spaces_  
\[V_{n}:=V_{(n,\ldots,n)}=\bigoplus_{|\mathbf{I}|_{\infty}\leq n}W_{\mathbf{i}},\]  
where each function \(f\in V_{n}\) can be represented as  
\[f(x)=\sum_{|\mathbf{I}|_{\infty}\leq n}\sum_{ \begin{subarray}{c}\mathbf{1} \leq i\leq 2^{-\mathbf{i}},\\ i_{j}\text{ odd }\forall\mathbf{1}\leq j\leq d\end{subarray} }\alpha_{ \mathbf{i},\mathbf{i}}\cdot\Phi_{\mathbf{i},\mathbf{i}}(x), \tag{9}\]  
and \(\alpha_{\mathbf{i},\mathbf{i}}\in\mathbb{R}\) are the coefficients of the representation in the hierarchical tensor product basis. We can generalize the hierarchical representation (9) to different levels of discretization \(\mathbf{k}\) per dimension, i.e., \(f\in V_{\mathbf{k}}\), by replacing \(|\mathbf{I}|_{\infty}\leq n\) in the first sum by \(l_{i}\leq k_{i},\forall\mathbf{1}\leq j\leq d\). Now consider the \(d\)-linear interpolation of a function \(f\) by a \(f_{n}\in V_{n}\), i.e., a representation as in (9). For illustration, we look at the linear interpolation in one dimension; for the hierarchical coefficients \(\alpha_{i,j}\), \(l\geq 1\), \(i\) odd, it holds  
\[\alpha_{i,i} =f(x_{l,i})-\frac{f(x_{l,i}-h_{l})+f(x_{l,i}+h_{l})}{2}=f(x_{l,i}) -\frac{f(x_{l,i-1})+f(x_{l,i+1})}{2}\] \[=f(x_{l,i})-\frac{f(x_{l-1,(i-1)/2})+f(x_{l-1,(i+1)/2})}{2}.\]  
This illustrates why the \(\alpha_{i,j}\) are also called _hierarchical surplus_: they specify what has to be added to the hierarchical representation from level \(l-1\) to obtain the one of level \(l\). We can rewrite this in the following operator form  
\[\alpha_{i,i}=\left[-\frac{1}{2}\quad 1\quad-\frac{1}{2}\right]_{l,i}f\]  
and with that we generalize to the \(d\)-dimensional hierarchization operator as follows,  
\[\alpha_{\mathbf{i,j}}=\left(\prod_{t=1}^{d}\left[-\frac{1}{2}\quad 1\quad- \frac{1}{2}\right]_{l,i_{t}}\right)f. \tag{10}\]  
We denote \(\mathbf{H}\) with the _hierarchization operator_ that performs the transformation (10) from the nodal function values of \(f\in V_{n}\) to obtain all the arising hierarchical values \(\alpha_{\mathbf{i,j}}\). The inverse operator \(\mathbf{E}=\mathbf{H}^{-1}\) is called the _dehierarchization operator_ and computes from the hierarchical values \(\alpha_{\mathbf{i,j}}\) the corresponding (nodal) function values \(f\) on all the grid points.