# Finite Differences on Sparse Grids for Continuous-Time Heterogeneous Agent Models
## 3 Sparse Grids
### Finite Difference Schemes on Sparse Grids  
Finite differences on sparse grids were introduced and studied in [5], where consistency proofs and convergence results are given; see also [6; 7; 33]. The construction of finite difference operators is based on a dimensional splitting combined with the nodal to hierarchical basis transformation (10) and its respective back-transform. Let us first describe the original sparse grid finite difference approach, where operators are a composition of three partial operators [5]:  
* A basis transformation from nodal to hierarchical basis (10) in all dimensions but the dimension \(j\), in which we aim to use the finite difference stencil. * Application of a finite difference stencil in dimension \(j\) with mesh size given as the local step size to the neighboring grid point in dimension \(j\). * A basis transformation from hierarchical to nodal basis, i.e., reverse of (10), in all dimensions but dimension \(j\). The finite difference operators use per dimension the neighboring grid points of the respective grid point, i.e., the closest grid points in the dimension. For the approximation of the derivative on regular sparse grids, one uses appropriate equidistant difference stencils. If adaptive refinement, as later explained in Section 3.2, is used, the grid points in the different dimensions are no longer equidistant, that is the distance can no longer be defined based on the grid refinement level, but the stencil is still chosen such that the closest neighbors in the respective dimensions are used. We consider an alternative approach [9], which employs additional points and is simpler to implement since it only involves function evaluations. Instead of using the function values on the sparse grid points, one interpolates on nodes that we will refer to as _ghost nodes_. This way we do not have to use basis transformations such as (10) and one could simply take any sparse grid library, such as SG++ [32], to implement this approach. To describe the approach from [9], we first define the above noted ghost points. Afterwards, we describe interpolation operators working on these points. Finally, we introduce the finite difference operators by using these interpolation operators. To define ghost nodes, we start by defining the _ghost node step size_. **Definition 1** (Ghost node step size). : _We define the ghost node step size \(h_{g_{j}}\) in dimension \(j\), \(1\leq j\leq n\), for a grid point \(x_{1,i}\) by \(h_{g_{j}}:=2^{-k_{j}}\) where \(k_{j}\) denotes the maximal level used in dimension \(j\)._  
Note that this is half of the size of the smallest support of the basis functions in this dimension. This makes sense since for this step size the local behavior of the approximation is still captured. For adaptive sparse grids, one could also take a bigger distance in some grid points, but due to the linearity of the approximation in this part, this does not change the result. Note that for the different sparse grid operators, we need to interpolate on different points. For the forward difference, we have to add the ghost node step size in the respective dimension and for the backward difference we have to subtract it in the respective dimension. We refer to them as _forward difference ghost nodes_ and _backward difference ghost nodes_. Examples for forward difference ghost nodes are given in Figure 1. Notice that for the second derivative finite difference, we can, as usual, employ the first derivative operators twice. Other difference operators are possible but we restrict ourselves for a simplified presentation. **Definition 2** (Ghost node).