## Non-uniform grids

When we discretize a Partial Differential Equation (PDE) in order to solve it numerically with the finite difference method, we need to decide on a grid of points on which to perform the discretization. This can be either uniform, i.e. with the points equally spaced within the range we are solving for, or graded. This applies to one-dimensional problems (as is the case here), or multidimensional ones in which case the points can have a different distribution along the axes of each dimension. The advantage of non-uniform grids is that they can cluster points around the more problematic or "error-prone" areas. These would be areas with locally high derivatives, caused for example by a discontinuity in the initial conditions (like around the strike of a vanilla option where the first derivative is discontinuous), or a boundary condition forcing the solution to zero, like near an knock-out barrier. A balance has to be hit between the amount of clustering and the non-uniformity it comes with as a price. The grid spacing needs to be changing gradually enough so as to not result in loss of accuracy due to the gradation itself. Custom grid profiles are utilized in the pricer which were kind of optimized(?) for vanilla and continuously monitored barrier options when I first wrote this app more than a decade ago. The non-uniformity was kept pretty mild with the overall aim being to keep the average error low across the whole asset range plot. Moreover, the clustering is always centered at either the strike or a barrier. This may not be optimal in a real-life pricing scenario where we would like to focus on and maximize accuracy for the actual asset spot. So for the recently added discretely monitored barrier options I have done just that, that is allow the user to focus the grid clustering around the chosen asset spot. More on how well this works here.

The Asian option pricing module uses the vanilla grid generator. As a result, the clustering is not always correctly focused where the largest gamma occurs with Asian options. In a more polished implementation the grid generator would predict the area of highest curvature in each case. That said they still work pretty well as can be seen below.

In an option pricing problem we have one or more "spatial" dimensions corresponding to the underlying(s) that the contract involves and of course the temporal dimension. As a parenthesis (maybe needed since I have found that this is confusing some people), it must be noted that the same is not true on the implementation level of the Monte Carlo method. In that case the dimensionality of the problem is actually the number of underlyings, or more generally stochastic factors, multiplied by the number of time points we need to simulate each factor's path on. I've often had a hard time convincing some of my (non-quant) past colleagues that this is indeed the case!

In the current implementation non-uniform grids are used for the spatial dimensions only, i.e. for the discretization of the underlying asset (and also for the running average in the case of Asian options). The time grid is always uniform. Actually this is not strictly true when were are using the smoothing technique called Rannacher time-stepping which can be seen in action here.

When we discretize a Partial Differential Equation (PDE) in order to solve it numerically with the finite difference method, we need to decide on a grid of points on which to perform the discretization. This can be either uniform, i.e. with the points equally spaced within the range we are solving for, or graded. This applies to one-dimensional problems (as is the case here), or multidimensional ones in which case the points can have a different distribution along the axes of each dimension. The advantage of non-uniform grids is that they can cluster points around the more problematic or "error-prone" areas. These would be areas with locally high derivatives, caused for example by a discontinuity in the initial conditions (like around the strike of a vanilla option where the first derivative is discontinuous), or a boundary condition forcing the solution to zero, like near an knock-out barrier. A balance has to be hit between the amount of clustering and the non-uniformity it comes with as a price. The grid spacing needs to be changing gradually enough so as to not result in loss of accuracy due to the gradation itself. Custom grid profiles are utilized in the pricer which were kind of optimized(?) for vanilla and continuously monitored barrier options when I first wrote this app more than a decade ago. The non-uniformity was kept pretty mild with the overall aim being to keep the average error low across the whole asset range plot. Moreover, the clustering is always centered at either the strike or a barrier. This may not be optimal in a real-life pricing scenario where we would like to focus on and maximize accuracy for the actual asset spot. So for the recently added discretely monitored barrier options I have done just that, that is allow the user to focus the grid clustering around the chosen asset spot. More on how well this works here.

The Asian option pricing module uses the vanilla grid generator. As a result, the clustering is not always correctly focused where the largest gamma occurs with Asian options. In a more polished implementation the grid generator would predict the area of highest curvature in each case. That said they still work pretty well as can be seen below.

In an option pricing problem we have one or more "spatial" dimensions corresponding to the underlying(s) that the contract involves and of course the temporal dimension. As a parenthesis (maybe needed since I have found that this is confusing some people), it must be noted that the same is not true on the implementation level of the Monte Carlo method. In that case the dimensionality of the problem is actually the number of underlyings, or more generally stochastic factors, multiplied by the number of time points we need to simulate each factor's path on. I've often had a hard time convincing some of my (non-quant) past colleagues that this is indeed the case!

In the current implementation non-uniform grids are used for the spatial dimensions only, i.e. for the discretization of the underlying asset (and also for the running average in the case of Asian options). The time grid is always uniform. Actually this is not strictly true when were are using the smoothing technique called Rannacher time-stepping which can be seen in action here.

The above slides display the solution's numerical error distribution across the whole grid. We are normally interested in the value of an option for the current asset spot price, but by solving a PDE we do get a valuation for the whole range. The errors represent the difference from the analytical solution for the vanilla and the barrier options and from a reference solution for the Asian option (calculated separately on a very high resolution grid). A relatively small time step was used in all cases so that the error due to the time-discretization doesn't interfere with the results.

It can be seen that using the non-uniform grid considerably flattens the error curve across the "moneyness" of the option. That said, it cannot always guarantee a more accurate valuation for a particular asset spot. This is the case for the vanilla option where more grid points have been placed around the strike (where the curvature of the solution is highest). While this clearly suppresses the discretization error overall, it just so happens that the uniform grid error is at its minimum for an at-the-money option, i.e. when the asset spot equals the strike, while with the non-uniform grid it is at a local maximum! This is of course the simplest option and model there is and in general we will not know where we are in the error graph (plus in general it looks different for different option parameters). Nevertheless the above presentation shows non-uniform grids to be generally better performing and I think they should be the default choice. This does not tell the whole story though. When a larger time step is used (as one may do in practice) and the time-discretization error becomes significant, the situation becomes less clear-cut and any benefit from the non-uniform grid can be "washed away". Feel free to play around with the different parameters and see for yourselves.

It should be noted that for the Asian option case we use the same discretization for the running average (A) planes as we do for the asset grid, i.e. more asset planes are clustered around the strike based on the same grid generating function. Quadratic interpolation for A was used in the above examples (the algorithm needs to interpolate between solutions based on different A planes).

Finally it can be seen that the valuations are almost instantaneous, even for the Asian option, so one could ask if non-uniform grids are worth the effort since we could just increase the uniform grid resolution a little and achieve the same result in no time. While this may be the case with the simple problems covered here, when we go to more complicated 2,3 or 4-dimensional contracts then we could really save some time. After that we would just use Monte Carlo instead.

You can reproduce the above tests, or experiment further if you wish, using the standalone pricer (free beta version for Windows PCs).

It can be seen that using the non-uniform grid considerably flattens the error curve across the "moneyness" of the option. That said, it cannot always guarantee a more accurate valuation for a particular asset spot. This is the case for the vanilla option where more grid points have been placed around the strike (where the curvature of the solution is highest). While this clearly suppresses the discretization error overall, it just so happens that the uniform grid error is at its minimum for an at-the-money option, i.e. when the asset spot equals the strike, while with the non-uniform grid it is at a local maximum! This is of course the simplest option and model there is and in general we will not know where we are in the error graph (plus in general it looks different for different option parameters). Nevertheless the above presentation shows non-uniform grids to be generally better performing and I think they should be the default choice. This does not tell the whole story though. When a larger time step is used (as one may do in practice) and the time-discretization error becomes significant, the situation becomes less clear-cut and any benefit from the non-uniform grid can be "washed away". Feel free to play around with the different parameters and see for yourselves.

It should be noted that for the Asian option case we use the same discretization for the running average (A) planes as we do for the asset grid, i.e. more asset planes are clustered around the strike based on the same grid generating function. Quadratic interpolation for A was used in the above examples (the algorithm needs to interpolate between solutions based on different A planes).

Finally it can be seen that the valuations are almost instantaneous, even for the Asian option, so one could ask if non-uniform grids are worth the effort since we could just increase the uniform grid resolution a little and achieve the same result in no time. While this may be the case with the simple problems covered here, when we go to more complicated 2,3 or 4-dimensional contracts then we could really save some time. After that we would just use Monte Carlo instead.

You can reproduce the above tests, or experiment further if you wish, using the standalone pricer (free beta version for Windows PCs).