Higher Order PDEs and the Curse of Dimensionality

Higher Order PDEs and the Curse of Dimensionality When pricing multi-factor derivatives products the general consensus is that the partial differential equation (PDE) and finite difference (FDM) approaches become difficult to apply and we usually resort to other methods such as Monte Carlo or numerical integration in multiple dimensions. In this blog I will attempt to describe some of the essential problems that we encounter when approximating higher-order PDE (in the current case, two and three dimensions) by popular FD schemes; we claim that the ADE method is easy to implement and can be parallelized for shared memory systems.

The main topics are: Formulating a PDE in an unambiguous manner FD schemes for multi-factor PDEs Implementation in C++, using Boost data structures and multithreaded programming

In principle, writing down the Black Scholes PDE in n dimensions is the easy part. The complications arise when we define the corresponding boundary condition information. First, we need to either truncate the region of interest or alternatively we can transform the original region to the unit cube in n dimensions. This latter technique is general and robust and it can be used instead of, or in combination with domain truncation. Next, the specification of boundary conditions is made easier by the application of the Fichera theory (which can be seen as a generalization of the well-known Feller condition, especially for the near field and even for the far field when using domain transformation.) Having defined the PDE problem, we now choose to approximate it using finite differences. For multi-dimensional PDEs we see that the ADI method is popular, while in recent years the Splitting method has been used because of its flexibility in solving complex PDEs. Both methods are examples of MOS (multiplicative operator splitting) methods which implies that we solve a complex PDE as a sequence of simpler, one-dimensional PDEs.

The main disadvantages of MOSs are:

. They introduce splitting error; it is possible that you end up with a first-order accurate approximation to the PDE which is not what we want

. It is difficult to parallelise these schemes; another challenge is to parallelise the tridiagonal LU solver that each leg of the schemes uses. This is a major botteleneck. . The ADI method in combination with the Crank-Nicolson scheme (for time discretisation) and the Craig-Sneyd method (for mixed derivatives) can produce oscillations and inaccuracies in certain situations

. The specification of conforming boundary conditions (especially for solutions at intermediate time steps) can be problematic

The approach that we have been using is based on AOS (additive operator splitting) and it allows us to write a PDE problem as the sum of partial solutions to the PDE in question (an example of an AOS is the Alternating Direction Explicit(ADE) method which I described in a recent SSRN paper). The advantages of AOS are:

. The schemes are uniformly stable, explicit and second-order accurate

. No splitting error is introduced and no artificial boundary conditions need be defined

. The scheme is easily parallelized, for example in combination with the C++ OpenMP library

. When implementing high-dimensional PDEs we use the Boost multi_array library which reduces the cognitive burden on the developer

. The method can be used for problems involving mixed derivatives; in these cases we use the Yanenko variant for approximation these terms.

We conclude with a discussion of the accuracy of the ADE scheme and some remarks on speedup.

http://papers.ssrn.com/sol3/papers.cfm?abstract_id=1552926

In the above article we introduce the theory underlying ADE and we use it to price European and American options. We have also generalized the method to two and three factor (basket) options. The method is accurate, easy to program and is amenable to coarse parallelism. To date, we have seen that the speedup with ADE is between 3 and 5 times that experienced with ADI or Splitting methods which are difficult to parallelise. These are the initial remarks and findings. I will report on these issues in future articles.