I want to present Octave / Matlab code for pricing american equity option with the Willow Tree (WT) model.The WT model is a lattice based models, where the number of nodes per time step is fixed. The transition probabilities between the nodes are optimized to fulfill no arbitrage conditions. The biggest advantage is the fast valuation on the lattice because of the smaller number of total nodes compared to a bi/trinomial lattice model.One drawback is the need for optimization of the transition probabilies. Although this optimization has to be done only once for a discrete set of [nodes,timesteps, maturity], this is a limitation in practical implementations.You find the Octave code here (no special packages are needed, tested with Octave > 3.6.1):click hereI am neither quant nor English native speaker, so please just ask if I expressed myself in an inconsistent way :)To understand possible applications of the model, I will give you some background:- I am working in the risk management industry on the implementation of internal models of asset managers, banks and insurance companies- I am using for my private trading a market risk tool based on a full valuation Monte-Carlo approach with 50000 scenarios - this market rist tool is completely written in Octave, therefore all pricing functions have also be written in Octave for maintenance reasons.- the tool is used for risk assessment of trading of European (right now) and (in the future) American options. As risk measures Value at risk, expected shortfall and stress scenario values are calculated- most important is speed > accuracy. In risk management I am more interested in the delta between stressed scenario and base scenario than in the absolute level (in any case a calibration of the model values to observed market values is performed). The WT methods yields accuracy in the range of <0.5% compared to the binomial model for american option pricing, which is absolutely sufficient for my use case.- to keep the calculation fast, full vectorization of any implementation has to be possible. As input data, 50000x1 vectors have to be accepted.The last point is the reason why binomial lattice models don't work for my use case - the memory consumption for parallel computation of 50000 scenarios, decent time step size (1 or 2) and up to 180 days to maturity is way to large -> another solution has to be foundThis was the reason for the implementation of the WT model.My intention is that- you have a code of the working WT model (I couldn't find any working code on the internet)- perhaps somebody is debugging the code and / or finds it useful- you can give me hints for other faster methods of american option pricing, which can be implemented in Octave (full vectorization, 50000 scenarios)The implementation is based on the literature:Quote"Willow Tree", Andy C.T. Ho, Master thesis, May 2000"Willow Power: Optimizing Derivative Pricing Trees", Michael Curran, ALGO RESEARCH QUARTERLY, Vol. 4, No. 4, December 2001My own model verifications and the papers suggest that the WT model yields quite accurate results for time step sizes in the range of 2 to 5 days and for 20 to 30 nodes per time step. Therefore I included optimized p and z values to approximate a normal distribution for nodes ranging from 10 to 50 values, which should be sufficient for fast and accurate pricing.For practical purposes, one would pre-optimize for stand sets of maturities / time step sizes / number of nodes and store the transition propabilities in a database or specific structure. Curran provides formulas for interpolation of transition probabilities between pre-optimized time steps.The implementation right now is for equity options only, but in principle you can include any stochastic process for your underlying financial instruments (like IR rates etc.)Comments and critics welcome!Best,Schinzilord

This is pretty much a waste of time - much as I like Michael Curran's work on Asian and Basket options, this is less worthwhileFifteen years is about three generations of better numerical methods - much better to code up ideas from 2014 or 2015

Got it - I have a reference.Do you have code samples for actual faster / more accurate pricing functions?I have no overview on recent literature / academic standard.

QuoteOriginally posted by: SchinzilordGot it - I have a reference.Do you have code samples for actual faster / more accurate pricing functions?I have no overview on recent literature / academic standard.There are some methods hereWe now wait for Spursfan to come up to the plate. // I am not familiar with Willow Tree but I do remember someone telling me that it was fast. ====The early exercise problem is nonlinear so an exact solution is not possible; then, a nonlinear system needs to be solved using some iterative method. Some of them are quite slow.

Mark Joshi has co-authored papers on the best choice of parameters for binomial trees if you're looking for something similar

QuoteOriginally posted by: spursfanMark Joshi has co-authored papers on the best choice of parameters for binomial trees if you're looking for something similarAlso for 2-factors? There is also more to life than binomial?

Nope

QuoteOriginally posted by: spursfanNopeSo, binomial method for 2-factor American options is an open/unsolved problem? QuoteFifteen years is about three generations of better numerical methods - much better to code up ideas from 2014 or 2015 I should hope so. I am more skeptical myself. But there is somewhat of a lag compared to other disciplines when it comes to numerical methods. It feels like a time warp, e.g. using Rannacher and Crank all the time.

Thank you both yor your input.My constraints are:- I am restricted to Matlab / Octave code- Matlab is fast only for fully vectorized code- to me it seems that I cannot fully vectorize (e.g. get rid of costly for loops via all Monte-Carlo Scenarios) finite difference or other fancy models based on some optimization, LU decomposition, inverting matrices etc.For C++ code one could use of the techniques you showed in your papers, Cuchulainn, and get fast enough pricing.But since I am restriced to the models where I can fully operate on vectors / matrices, I will investigate the tree truncation further. Perhaps I can speed up the binomial option pricing codes.Until then, I am restricted to the WT model. My wasted time are treated as sunk costs

I don't know Willow, but found QuoteWhen we compare the performance of the willow tree to the trinomial tree (the industry standard), models based on willow tree are much faster, more accurate, and more stable.?

That is nonsense to me.It is faster for either- massive parallel computation- of if you already have pre optimized transition probabilitiescompared to bi/trinomial trees.Neither it is more stable nor more accurate, that is just plain wrong to me.Interestingly, the WT method is implemented in risk management software like "IBM Algo One". Perhaps Curran worked (as a consultant / employee ?!? I am just speculating) for Algorithmics in the late 1990s. Algo also uses some numerical methods for Asian option pricing, where Curran is referenced as (Co-)Author.The literature is not very broad for Willow trees, the two links I provided cover most (all?) of the topic. Some Bachelor / Master thesis are around, mostly done in cooperation with some institutions who use Algo software.

Matlab implementations for several methods for pricing options (also American) are compared in the recent paperL. von Sydow, L.J. Höök, E. Larsson, E. Lindström, S. Milovanovic, J. Persson, V. Shcherbakov, Y. Shpolyanskiy,S. Siren, J. Toivanen, J. Walden, M. Wiktorsson, J. Levesley, J. Li, C.W. Oosterlee, M.J. Ruijter, A. Toropov, and Y. Zhao:BENCHOP - The BENCHmarking Project in Option Pricing,International Journal of Computer Mathematics, Volume 92, Issue 12, 2015, pp. 2361-2379.Also the Matlab codes are available under the web page www.it.uu.se/research/project/compfin/benchop

QuoteOriginally posted by: TeneMatlab implementations for several methods for pricing options (also American) are compared in the recent paperL. von Sydow, L.J. Höök, E. Larsson, E. Lindström, S. Milovanovic, J. Persson, V. Shcherbakov, Y. Shpolyanskiy,S. Siren, J. Toivanen, J. Walden, M. Wiktorsson, J. Levesley, J. Li, C.W. Oosterlee, M.J. Ruijter, A. Toropov, and Y. Zhao:BENCHOP - The BENCHmarking Project in Option Pricing,International Journal of Computer Mathematics, Volume 92, Issue 12, 2015, pp. 2361-2379.Also the Matlab codes are available under the web page www.it.uu.se/research/project/compfin/benchopThis is like a committee? Seriously, this project idea has (big) potential if its scope can be extended beyond the confines of Matlab. For instance, input and output data formats and computed values could be made interoperable and can be read by other software systems. With a focused set of system features you could provide standardized regression-based test beds that others can test their methods against. It would be a good project for some of the millions of MSc/MFE students out there.

My post is a mistake. It was a few open forum windows and put my post in a wrong one. Sorry

@Tene:Thank you for the link.They write in their paper:QuoteThe codes are not fully optimized, and the numerical results should not be interpreted as competition scores. We rather see it as a synoptical exposition of the qualities of the different methodsSo it may be interesting to get an overview of methods, but the code cannot be used as a performance benchmark (what I though in my first post before editing, since "BENCHOP" sounds a litte bit focussing on speed, not only on sophisticated methods.I am still looking for optimized Matlab / Octave code to calculate the value of >10000 (e.g. 100000) American equity options as fast as possible. Performance > accuracy. Edited due to misunderstand of BENCHOP. Edit 2:I really do not get why to give calculation time of not optimized code (57seconds option pricing of MC with a LOOP through all time steps, really?). And then they give the calculation time in their paper....for what purpose?That is like putting trailers to formula 1 cars with unknown weight and then comparing the time for one round trip...