L-S Algorithm - American Options C++ Speed?

[Hob]

Hi all,

I have written a least squares regression algorithm based on the 2001 L-S paper. I have bench marked it with the very basic numerical example given in the paper.

My main concern is when comparing with the American option prices, L-S claimed to have used 100,000 paths (50,000 plus 50,000 antithetic) with 50 exercise points per year. I was wondering if anyone had conducted a speed test for the examples used?

My code struggles to execute this quickly even for a low number of sample paths (10,000). The actual path generation is fairly quick (~ seconds) but solving the matrices for the regression step at each point really kills the speed.

Many thanks,

Hob

 

[Daniel Duffy]

Quick answer/question .. did you profile each of the steps to pinpoint the algorithm? It might be doing funny things with matrices.

Which language are you using?

 

[Hob]

Hi Daniel, it is written in C++, I'm using pre written code (Eigen) to handle the matrices. Roughly how long should the LSM algorithm take for 100k paths?

 

[Daniel Duffy]

Hi Daniel, it is written in C++, I'm using pre written code (Eigen) to handle the matrices. Roughly how long should the LSM algorithm take for 100k paths?

Hi Hob,
I don't have the numbers to hand just now but my co-author Dr. Joerg Kienitz (C++ MC Frameworks) has a chapter + code for LSLS using the matrix classes that I built.

If you can give the full parameter set I can have a shot at it.

Dr. Nick Webber in his VBA book also has LSLS.

thanks

 

[Hob]

Hi Hob,
I don't have the numbers to hand just now but my co-author Dr. Joerg Kienitz (C++ MC Frameworks) has a chapter + code for LSLS using the matrix classes that I built.

If you can give the full parameter set I can have a shot at it.

Dr. Nick Webber in his VBA book also has LSLS.

thanks

Hi Daniel, thanks for the link to your book, I will have a look at it.

The parameters are:
Spot Price: $36.00
Volatility: 20%
Time: 1 Year
Risk Free: 6%
Strike Price: $40.00
n: 100,000
Exercise Times: 50

Simulated Price: 4.472 (from LSM Algorithm), Finite Difference (4.478).

Regards,

Hob

 

[Hob]

I noticed the problem (actually 2), the first is the compiler wasn't set for optimizing the code speed. The second was that the matrix size was using the total paths not just the in-the-money paths.

 

[Daniel Duffy]

I noticed the problem (actually 2), the first is the compiler wasn't set for optimizing the code speed. The second was that the matrix size was using the total paths not just the in-the-money paths.

Indeed! By default, VS creates a debug project which is in this case is real slooooooow LOL, I forgot myself.

I'll get back with some data (run code in MC book).

BTW what is your typical running time now?

 

[Hob]

Indeed! By default, VS creates a debug project which is in this case is real slooooooow LOL, I forgot myself.

I'll get back with some data (run code in MC book).

BTW what is your typical running time now?

For ~1,000 paths it is around a few seconds, for ~10k a few minutes and ~10^6 is is very slow (around an hour), more than likely will need to optimize my code, but for now I am only doing a few tests.

On another note, I purchased your book and is very useful! On the basis choice (page 523 onwards), I was just wondering if the Figure 19.2 (page 524) was for a put option? It looks as if it is the Option Value vs. Underlying Stock plotted, but the Payoff line is for a call option?

Cheers,

Hob

 

[Daniel Duffy]

Hi Hob,
Thank you.

I ran the code accompanying(!) the book (in Release mode LOL) and get order of magnitude results the same as you. Joerg gives lower and upper bounds. In order to approximate American, I take Bermudans with 50 exercise dates and get roughly the same answer as my Trinomial case (BTW LS results on FDM p. 127 seem a bit off; they get 4.478, I get 4.48631). AFAIK LSM has some bias.

The authors state that LSM is easier to parallelise and this could be one way to improve speedup. And I don't like the if else in our NumberfPaths loop and I would 'invert' the loop. As wel as loop fusion if you have time etc.
Loop-level parallelism in OpenMP looks doable but we need to be careful with race conditions in RNG.
http://www.datasimfinancial.com/forum/viewforum.php?f=9&sid=9d639f837a0aea305762ab1c59f07ca1

Is is possible to price and regress in parallel by interleaving these two operations?

//A good student IMO is to use C++ 11, Boost Math Libary and parallel progamming to speed up and improve accuracy.

Have you tried it yet for a 20-factor swaption?


We use standard polynmials as basis functions but Legendre/Laguerre are mentioned by LS.

// I'll get back on the figures.

 

[Daniel Duffy]

On another note, I purchased your book and is very useful! On the basis choice (page 523 onwards), I was just wondering if the Figure 19.2 (page 524) was for a put option? It looks as if it is the Option Value vs. Underlying Stock plotted, but the Payoff line is for a call option?

correct.