# Finite Differences on Sparse Grids for Continuous-Time Heterogeneous Agent Models
## 3 Sparse Grids
### Finite Difference Schemes on Sparse Grids
: _For a grid point \(x_{1,i}\) in which we aim to compute the finite differences in dimension \(j\), \(1\leq j\leq d\), we define the corresponding forward difference ghost node by_  
\[g_{1,i}^{F,j}:=(x_{1,i_{1},i_{1}},\ldots,x_{l_{j},i_{j}}+h_{g_{j}},\ldots,x_{ l_{d},i_{d}})\]and similarly for the backward difference, we define the corresponding backward difference ghost node by_  
\[g_{\mathbf{l},\mathbf{i}}^{B,j}:=(x_{l_{1},i_{1},i_{1}},\ldots,x_{l_{j},i_{j}}-h _{g_{j}},\ldots,x_{l_{u},i_{d}}).\]  
The main idea of the construction of finite difference operators is simply to collect the terms that are considered constants under partial differentiation. When one computes partial derivatives, other variables are held constant by definition. Therefore, if a function is multiplicatively separable in other variables, one can just compute the derivative of the variable as in one dimension. As the set of basis functions are built from hierarchical functions in one dimension, the basis functions lead to separable functions. Without a loss of generality, we describe the finite difference operators in two dimensions with the derivative taken in the first dimension. The generalization to higher dimensions is straightforward using \(j\) for the dimension in which the derivative is taken and a multi-index \(-j\) represents all other dimensions besides \(j\). Using the fact that \(\phi_{l_{2},i_{2}}(x_{2})\) from \(\Phi_{(l_{1},l_{2}),(i_{1},i_{2})}(x_{1},x_{2})=\phi_{l_{1},i_{1}}(x_{1})\phi _{l_{2},i_{2}}(x_{2})\) does not depend on \(x_{1}\), and the linearity of the differential operator, we obtain  
\[\frac{\partial}{\partial x_{1}}f(x) = \frac{\partial}{\partial x_{1}}\sum_{(l_{1},l_{2}),(i_{1},i_{2}) \in\mathbb{I}_{n}}\alpha_{(l_{1},l_{2}),(i_{1},i_{2})}\phi_{l_{1},i_{1}}(x_{1 })\phi_{l_{2},i_{2}}(x_{2})\] \[= \frac{\partial}{\partial x_{1}}\left[\sum_{(\cdot,l_{2}),(\cdot,i_{2})\in\mathbb{I}_{n}}\phi_{l_{2},i_{2}}(x_{2})\cdot\left(\sum_{\{(l_{1}, l_{1}):(l_{1},l_{2}),(i_{1},i_{2})\in\mathbb{I}_{n}\}}\alpha_{(l_{1},l_{2}),(i_{1},i_{2}) }\phi_{l_{1},i_{1}}(x_{1})\right)\right]\] \[= \sum_{(\cdot,l_{2}),(\cdot,i_{2})\in\mathbb{I}_{n}}\phi_{l_{2},i_ {2}}(x_{2})\cdot\frac{\partial}{\partial x_{1}}\left(\sum_{\{(l_{1},i_{1}):(l _{1},l_{2}),(i_{1},i_{2})\in\mathbb{I}_{n}\}}\alpha_{(l_{1},l_{2}),(i_{1},i_{2 })}\phi_{l_{1},i_{1}}(x_{1})\right).\]  
Now, the expression in the \(()\)-brackets to be differentiated is an one-dimensional function of \(x_{1}\), on which any finite difference scheme can be applied to approximate the derivative. Using, e.g., the forward difference,  
\[\frac{\psi(x+h)-\psi(x)}{h},\text{ where }\psi(x):=\sum_{\{(l_{1},i_{1}):(l_{1}, l_{2}),(i_{1},i_{2})\in\mathbb{I}_{n}\}}\alpha_{(l_{1},l_{2}),(i_{1},i_{2})} \phi_{l_{1},i_{1}}(x_{1}), \tag{12}\]  
we can now define a finite difference operator on sparse grids that is based on interpolation at \((x_{1},x_{2})\) and \((x_{1}+h,x_{2})\). For a given grid and the desired difference operator, we can simply consider all respective ghost nodes arising from \((x_{1}+h,x_{2})\) and interpolate on these. Figure 1: Visualization of the ghost points for the forward difference in \(x\)-dimension. **Left**: the ghost node (red) that is used for the sparse grid forward finite differences in \(x\)-dimension in the green grid point. **Right**: all forward difference ghost nodes that are used for the sparse grid are drawn in red. On the boundary, the red ghost nodes coincide with existing grid points, while in the interior function interpolation has to be used on the ghost nodes. **Definition 3** (Interpolation-based sparse grid finite difference operator). : _Let us formally denote the interpolation operator to be evaluated on \(x_{\mathbf{i},\mathbf{i}}\) on the sparse grid by_  
\[\mathbf{I}_{s}:\bigoplus_{\mathbf{k}=\mathbf{1}}^{1}W_{\mathbf{k}}\to V_{ \mathbf{I}},\]  
_which is essentially (11) for \(V_{\mathbf{I}}\).