SERVING THE QUANTITATIVE FINANCE COMMUNITY

 
User avatar
Cuchulainn
Posts: 53314
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

Re: American options -- Reference prices

September 24th, 2017, 11:30 am

Cuchulainn wrote:
some test output

/*  S  exact delta CN delta    Spline delta exact gamma CN gamma    Spline gamma
59     0.330935233 0.330702564 0.330478248  0.040967715 0.04098453  0.041068871
60     0.372482798 0.372232265 0.372093554  0.042043376 0.042074873 0.042161739
61     0.41484882  0.414593361 0.414541127  0.042603904 0.042647319 0.042733408
62     0.457519085 0.457270132 0.457302102  0.042654217 0.042706223 0.042788541
63     0.499993235 0.499760129 0.499871257  0.042216737 0.04227377  0.042349769
64     0.541801022 0.541590678 0.541773643  0.041328768 0.041387329 0.041455004
65     0.582515647 0.582332471 0.582578239  0.040039354 0.040096257 0.040154187
66     0.62176381  0.621609821 0.621908227  0.038405882 0.038458444 0.038505789
67     0.659232357 0.659107471 0.659447781  0.036490702 0.036536856 0.03657332
68     0.694671633 0.694574052 0.694945475  0.034357967 0.034396306 0.034422069
69     0.727895851 0.727822509 0.728214631  0.032070838 0.032100608 0.032116243
70     0.758780913 0.758727922 0.759131055  0.029689185 0.029710218 0.029716604
71     0.787260172 0.787223244 0.787628682  0.027267796 0.027280425 0.027278649*/
 
Table.1 Output from Steps 1-4; data is K = 65, T = 0.25, r = b = 0.8, v = 0.3,NS = 325, NT = 1000

I wrote this up, triggered by Billy7's nice remark.
//

Examining the accuracy of the results in Table 1 we see that both the Crank Nicolson and cubic spline interpolator produce similar results for delta while the interpolator’s accuracy for gamma is less accurate than the Crank Nicolson method. What is the reason? For smooth functions centred divided difference approximation to the first and second derivatives result in second order accuracy. This approach is based on Taylor expansions. Cubic splines are polynomials and they are a third-order accurate approximation to a smooth function. The first derivative of the spline is a second-order approximation to the exact delta while the second derivative of the spline is a first-order approximation to the exact gamma. This theoretical result is proven mathematically in Alberg, Nilson and Walsh 1967, Theorem 3.11.1, page 94. But cubic spline interpolators can overshoot in order to always create a visually pleasing curves and this might account for the fact that the values for gamma are larger than the exact gamma or even the Crank Nicolson gamma.

When approximations to the second derivatives of a smooth function are needed, we can first approximate it by using the values of the first derivative as input in order to compute an approximation to the second derivative. This is called spline-on-spline computation (Hildebrand 1974, page 492 and Alberg, Nilson and Walsh 1967, pages 48-50) and the improvements in accuracy are visible. In the current case a useful  exercise would be to compare the values for gamma based on this variant and the original approach taken to produce the results in Table 1.
http://www.datasimfinancial.com

“Sir Walter Scott created rank & caste in the South and also reverence for and pride and pleasure in them"

Mark Twain
 
User avatar
Billy7
Posts: 255
Joined: March 30th, 2016, 2:12 pm

Re: American options -- Reference prices

September 24th, 2017, 11:33 am

Cuchulainn wrote:
Billy7 wrote:
Thanks. I've had a look and this makes sense if what's been done inside the loop is very simple (so that the loop overhead itself is significant in comparison. So, I may be wrong,but I find it very hard to believe that such a programming trick can give a 30 x speed increase.Though it would be great of course. 

You're welcome. It's worth a try. 
It depends on cache size, e.g. a block size of 3 is no good (I use bs = 2) and putting the penalty term in => same performance as unrolled case. In MOL.
I got lucky. I can try it on ADE,. A CN test would be nice.

Yes, it must be a cache thing mostly.
 
User avatar
Cuchulainn
Posts: 53314
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

Re: American options -- Reference prices

September 24th, 2017, 11:38 am

He has also a paper on UVM where he seems to be doing a fix point iteration to solve for the solution. I think this is not needed.

When it works, it's great especially in conjunction with Aitken acceleration. But the key issue is the the equation

x = f(x)

must be a contraction for it to work. aka df/dx < 1 in absolute value.

I would say other approaches are more accessible.

BTW I have Meyer's book, is is all discussed there?
http://www.datasimfinancial.com

“Sir Walter Scott created rank & caste in the South and also reverence for and pride and pleasure in them"

Mark Twain
 
User avatar
Cuchulainn
Posts: 53314
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

Re: American options -- Reference prices

September 24th, 2017, 12:01 pm

Billy7 wrote:
Cuchulainn wrote:
Billy7 wrote:
Thanks. I've had a look and this makes sense if what's been done inside the loop is very simple (so that the loop overhead itself is significant in comparison. So, I may be wrong,but I find it very hard to believe that such a programming trick can give a 30 x speed increase.Though it would be great of course. 

You're welcome. It's worth a try. 
It depends on cache size, e.g. a block size of 3 is no good (I use bs = 2) and putting the penalty term in => same performance as unrolled case. In MOL.
I got lucky. I can try it on ADE,. A CN test would be nice.

Yes, it must be a cache thing mostly.

Last week when we were discussing I got it going. Now I cannot reproduce the results :D
I believe Eigen has built-in unrolling.
http://www.datasimfinancial.com

“Sir Walter Scott created rank & caste in the South and also reverence for and pride and pleasure in them"

Mark Twain
 
User avatar
Billy7
Posts: 255
Joined: March 30th, 2016, 2:12 pm

Re: American options -- Reference prices

September 24th, 2017, 12:27 pm

berndL wrote:
Billy7 wrote:
So seems like Bulirsch Stoer doesn't quite damp oscillations in this case? What was the spatial resolution you used? What happens if you increase it?

By the way, I was looking at Meyer's paper on barrier options under stoch vol (http://people.math.gatech.edu/~meyer/PU ... option.pdf) and the timings seem quite odd to be honest. For example in table 2 he says that solving Heston with FD with resolution of NS=200, NV=100 and NT=200 takes 162 secs! That's crazy as even Kluge's 15-yr old online Heston pricer does that in less than 5 secs (my implementation does that in less than 1 sec on a budget laptop) . Meyer says the code was written in Fortran and run on a pretty fast Xeon so not sure what is going on there.

... His papers are a bit old....

I suspect that when people look at CPU timings in papers, especially papers a few years old, they tend to not place much importance on those timings (because they would have been produced on an old machine, with who knows what language, compiler, etc). I personally like to see if I can get at least some indication of performance out of such quotes if possible. That's why they're included in papers after all.
In Meyer's paper this seems possible indeed, since he clearly mentions that he used a high spec CPU (introduced in 2009, that would still be competitive with today's budget ones) and a high performance language (FORTRAN). Hence I raised the flag.
 
User avatar
Cuchulainn
Posts: 53314
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

Re: American options -- Reference prices

September 24th, 2017, 12:29 pm

The HMOL is starting to make more sense to me. Take

u_t = u_xx

and discretise in time to get something like

u_xx = au + F

Written as a 1st order system

v_x = au +F
u_x = v

Meyer solves this system using Riccati method.I had a look at my PhD thesis and I have 'sweeps' algorithm to solve by FDM.(lol)

Now the FDM approximate u and v to second order. Q. We can use v to get a good approximate the gamma (using splines on v or taking divided differences on v).

My scheme was based on this article (it's in Russian)
http://www.mathnet.ru/links/1cfdafddb1f ... mf6187.pdf
Last edited by Cuchulainn on September 24th, 2017, 12:37 pm
http://www.datasimfinancial.com

“Sir Walter Scott created rank & caste in the South and also reverence for and pride and pleasure in them"

Mark Twain
 
User avatar
Billy7
Posts: 255
Joined: March 30th, 2016, 2:12 pm

Re: American options -- Reference prices

September 24th, 2017, 12:31 pm

Cuchulainn wrote:
Billy7 wrote:
Cuchulainn wrote:
You're welcome. It's worth a try. 
It depends on cache size, e.g. a block size of 3 is no good (I use bs = 2) and putting the penalty term in => same performance as unrolled case. In MOL.
I got lucky. I can try it on ADE,. A CN test would be nice.

Yes, it must be a cache thing mostly.

Last week when we were discussing I got it going. Now I cannot reproduce the results :D
I believe Eigen has built-in unrolling.

:) Yes, I use Eigen sometimes when it makes things easier.
 
User avatar
outrun
Posts: 3913
Joined: April 29th, 2016, 1:40 pm

Re: American options -- Reference prices

November 21st, 2017, 10:20 pm

mj wrote:
I'd like to see some benchmarks for S is 120,K is 100, r=0.08, the volatilityis 0.2, the dividend rate q is 0.08, and the expiry T is 3This was studied in Quantitative Finance, Vol. 12, No. 1, January 2012, 17?20On the analytical/numerical pricing of American putoptions against binomial tree pricesMARK JOSHI and MIKE STAUNTONand was the subject of a certain amount of dispute. The price obtained there was5.929805

Browsing this thread today searching for Mark's material.
Thanks Mark for all the wonderful things you shared!
Image
 
User avatar
Cuchulainn
Posts: 53314
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

Re: American options -- Reference prices

December 13th, 2017, 11:23 am

Alan wrote:
Apparently we don't have a thread for this, so here is a good place to start.I am investigating convergence of some numerical methods and would appreciate it ifsomebody could confirm a 7-digit reference value under the Black-Scholes model.It is an American-style put option with [$]S_0 = K = 50[$], [$]T=1[$], [$]\sigma=0.40[$], and [$]r = 0.08[$] (no dividends).The put value is 6.299XXX; I need confirmation of the value I have for the 3 remaining digits, XXX.So as to not prejudice the answers, I'll give my value later in the thread.Thanks!

From another viewpoint, I tested using MOL C++ and Courant barrier function. I get
NS, P
2700, 6.299588
5400, 6.299595
10800, 6..299596
This also suggests that this approach can be applied to semlinear PDE. 
Of course if you want real speed ==> hand-crafted code. (+ Brennan Schwartz).
http://www.datasimfinancial.com

“Sir Walter Scott created rank & caste in the South and also reverence for and pride and pleasure in them"

Mark Twain
ABOUT WILMOTT

PW by JB

Wilmott.com has been "Serving the Quantitative Finance Community" since 2001. Continued...


JOBS BOARD

JOBS BOARD

Looking for a quant job, risk, algo trading,...? Browse jobs here...