[Cuchulainn]

More fitting of PDE

[Cuchulainn]

some more articles

[Cuchulainn]

ADE in PowerPoint 2003

[admin]

To appear

The Alternating Direction Explicit (ADE) Method for a Variety of One Factor Problems

Guillaume Pealat
Daniel J. Duffy

In this article we apply the ADE method to a number of partial differential equations in option pricing using one factor models (Black-Scholes, Local Volatility, Uncertain Volatility). We give a short background introduction to ADE and its variants, namely the Saul'yev, Larkin and Barakhat-Clark schemes. We discuss the stability, accuracy and performance of ADE for a generic one-factor partial differential equation. Of particular importance is how we transform problems on an unbounded domain to one on a bounded domain, thus avoiding complex mathematical techniques to find the optimal truncated boundary and the determination of the corresponding numerical boundary conditions.
The second part of the article examines a number of specific applications. First, we show that oscillation-free Greeks produced by the scheme makes ADE a suitable candidate for Uncertain Volatility Models. Second, we apply ADE to the problem of calibration of local volatility using the Kolmogorov forward equation and we show that the speed and the accuracy obtained makes ADE the method of choice over the popular Crank Nicolson method. Finally, we discuss some additional issues such as using exponential fitting to model extreme parameter values and how to design ADE to run using multithreaded code.

[admin]

remark; in nd only two sweeps are needed.

[admin]

The three ADE variants!

[Cuchulainn]

ADE for the 3d heat equation and Boost multiarray approach.

[Cuchulainn]

here is source code for the 1 factor ADE scheme which works with my FDM OO framework.

We have set up the same OO in C# whose publication is in progress.

[Cuchulainn]

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.

[Cuchulainn]

Here is the ADE article on SSRN

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

[Cuchulainn]

This article from some time back introduces the exponentially fitted method. It is used as part of ADE as component in the S variable.

[Cuchulainn]

Here is a working paper on ADE applied to one-factor equity pricing. Comments welcome.