Serving the Quantitative Finance Community

Cuchulainn
Posts: 64438
Joined: July 16th, 2004, 7:38 am
Location: Drosophila melanogaster
Contact:

Finite difference - CFD technique

The Yanenko book has been republished!THE METHOD OF FRACTIONAL STEPS by N. N. YanenkoMatched:The Method of Fractional Steps: the Solution of Problems of Mathematical Physics in Several Variables by Yanenko, Nikolaj N., Author Holt, M. TranslatorPaperback Springer. (2012)9783642651106.BRAND NEW PAPERBACK. \$143.08 Buy now at http://www.alibris.com/booksearch.detai ... -0-_-A-_-A Amazon
Last edited by Cuchulainn on September 13th, 2012, 10:00 pm, edited 1 time in total.
"Compatibility means deliberately repeating other people's mistakes."
David Wheeler

http://www.datasimfinancial.com
http://www.datasim.nl

Cuchulainn
Posts: 64438
Joined: July 16th, 2004, 7:38 am
Location: Drosophila melanogaster
Contact:

Finite difference - CFD technique

A compendium of FDM schemesKind of useful, in a nutshell.
"Compatibility means deliberately repeating other people's mistakes."
David Wheeler

http://www.datasimfinancial.com
http://www.datasim.nl

b4byZ
Posts: 54
Joined: September 6th, 2010, 2:17 pm

Finite difference - CFD technique

Hello, I am no familiar with FDM. I've got a number of questions: 1) Why is the FDM not suitable for barrier options? How about compound options where we have to solve for the critical asset price? Or other path-dependent options such as faders?2) Does the Crank-Nicolson produce better approximation than the explicit or the implicit? Is the explicit sufficient?Thank you.

Cuchulainn
Posts: 64438
Joined: July 16th, 2004, 7:38 am
Location: Drosophila melanogaster
Contact:

Finite difference - CFD technique

What is the difference between ADI and Soviet Splitting?
Last edited by Cuchulainn on October 13th, 2015, 10:00 pm, edited 1 time in total.
"Compatibility means deliberately repeating other people's mistakes."
David Wheeler

http://www.datasimfinancial.com
http://www.datasim.nl

Cuchulainn
Posts: 64438
Joined: July 16th, 2004, 7:38 am
Location: Drosophila melanogaster
Contact:

Re: Finite difference - CFD technique

The original Crank-Nicolson article for a nonlinear heat equation

http://citeseerx.ist.psu.edu/viewdoc/do ... 1&type=pdf
"Compatibility means deliberately repeating other people's mistakes."
David Wheeler

http://www.datasimfinancial.com
http://www.datasim.nl

Cuchulainn
Posts: 64438
Joined: July 16th, 2004, 7:38 am
Location: Drosophila melanogaster
Contact:

Re: Finite difference - CFD technique

https://onlinelibrary.wiley.com/doi/abs ... wilm.10366

In the WLD/DLW/LDW article and my C++ 2018 book we used the ADEB&C (Barakat Clark) version. This is a fast and accurate method even for NX = NY = 100, NT = 300 (e.g. T = 1, K = 60 it gives P = 1.732 in about .98 seconds on an old laptop. 35% of the computation is due to the specific form of the volatility function).
As a test, we took the original Saul’yev ADE method and it is 3 times faster than ADEB&C and also accurate. We take a novel FDM to solve the 1st order hyperbolic PDE at A = A_max. In the past many solvers (Asian, Cheyette) choked because of incorrect understanding of upwinding.  ADI is overkill in these cases as well as using similarity reduction techniques, possibly.
On a 2-core +hyperthreading (4 threads, essentially) we ran 8 calls of the solver using C++11 futures and the speedup was approximately 2.7. On bigger machines we can run even more instances.
We wish to use this model to generate training data for ML applications. But we don’t want to wait for 10 days for it to finish.  More like [4,10] hours by choosing a good algorithm, C++11 futures and “lots” of processors.
"Compatibility means deliberately repeating other people's mistakes."
David Wheeler

http://www.datasimfinancial.com
http://www.datasim.nl

JohnLeM
Posts: 515
Joined: September 16th, 2008, 7:15 pm

Re: Finite difference - CFD technique

The original Crank-Nicolson article for a nonlinear heat equation

http://citeseerx.ist.psu.edu/viewdoc/do ... 1&type=pdf
It seems that that they did not realized that their scheme is energy conservative in this paper. Very impressive work for a 1947 paper.

Cuchulainn
Posts: 64438
Joined: July 16th, 2004, 7:38 am
Location: Drosophila melanogaster
Contact:

Re: Finite difference - CFD technique

The original Crank-Nicolson article for a nonlinear heat equation

http://citeseerx.ist.psu.edu/viewdoc/do ... 1&type=pdf
It seems that that they did not realized that their scheme is energy conservative in this paper. Very impressive work for a 1947 paper.
This is related to the Cayley (unitary) form approximation to the exponential (Pade (1,1) 2nd order)

https://en.wikipedia.org/wiki/Cayley_transform

For Schrodinger 19.2.35
http://www.foo.be/docs-free/Numerical_Recipe_In_C/c19-2.pdf

It was only relatively recently in finance that Crank-Nicolson is only A-stable and not L-stable. There are 40 shades of snow. There used to be one.
The CN is not monotone, the holy grail of FDM.
"Compatibility means deliberately repeating other people's mistakes."
David Wheeler

http://www.datasimfinancial.com
http://www.datasim.nl

Cuchulainn
Posts: 64438
Joined: July 16th, 2004, 7:38 am
Location: Drosophila melanogaster
Contact:

Re: Finite difference - CFD technique

Consider the time-dependent Goursat problem

$\frac{\partial u}{\partial t} = \rho \frac{\partial^2 u}{\partial x \partial y}$, $0 \lt x,y \lt 1$

$\rho$ is a constant but it can be positive or negative.

The simple question: how to define well-posed boundary conditions for this problem?
"Compatibility means deliberately repeating other people's mistakes."
David Wheeler

http://www.datasimfinancial.com
http://www.datasim.nl

Alan
Posts: 10612
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

Re: Finite difference - CFD technique

Rotate coords by 45 degrees => standard 2D heat eqn in nice bounded region.
So any bc that works for the latter should work here, too.

Also, need some ic at a time slice, and then evolve soln either backwards or forwards depending on sign of rho.
Best to have the ic compatible with the bc at the edges.
Last edited by Alan on April 22nd, 2020, 7:20 pm, edited 1 time in total.

Paul
Posts: 11276
Joined: July 20th, 2001, 3:28 pm

Re: Finite difference - CFD technique

Rotate coords by 45 degrees => standard 2D heat eqn in nice bounded region.
So any bc that works for the latter should work here, too.
Nope.

Alan
Posts: 10612
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

Re: Finite difference - CFD technique

Why not?

Paul
Posts: 11276
Joined: July 20th, 2001, 3:28 pm

Re: Finite difference - CFD technique

Becomes

$\frac{\partial^2}{\partial \xi^2}-\frac{\partial^2}{\partial \eta^2} =\cdots$

Note minus sign.

Alan
Posts: 10612
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

Re: Finite difference - CFD technique

Cuchulainn
Posts: 64438
Joined: July 16th, 2004, 7:38 am
Location: Drosophila melanogaster
Contact:

Re: Finite difference - CFD technique

Yes. Paul is correct.
Goursat pde is hyperbolic and transformation turns it into a wave equation on RHS and a du/dt on LHS.

$\frac{\partial u}{\partial t} = \frac{\partial^2}{\partial \xi^2}-\frac{\partial^2}{\partial \eta^2} =\cdots$

I want to keep the original variables $x,y$ because of coupling to diffusion terms. BTW $(\xi,\eta)$ domain is a rhombus..

It is not elliptic so information is coming from only two of the sides of the domain. For $\rho \lt 1$ I can say that $x = 0, y = 0$ are where we have to define BC. It works in practice (FDM) and now in theory is next. Euler used this trick all the time, it's like plumbing. If it doesn't work in practice it don't work in theory.

BTW I have been unable to find any background on this. Even time-independent Goursat is few and far between (BTW in my 2018 C++ book I used this pde to compute the bivariate normal $M(a,b;\rho)$ ... just diferentiate the integral twice, very accurate).

Mixed derivatives are pesky, yes?
Last edited by Cuchulainn on April 22nd, 2020, 7:57 pm, edited 10 times in total.
"Compatibility means deliberately repeating other people's mistakes."
David Wheeler

http://www.datasimfinancial.com
http://www.datasim.nl