IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2303.02317.html
   My bibliography  Save this paper

Fast American Option Pricing using Nonlinear Stencils

Author

Listed:
  • Zafar Ahmad
  • Reilly Browne
  • Rezaul Chowdhury
  • Rathish Das
  • Yushen Huang
  • Yimin Zhu

Abstract

We study the binomial, trinomial, and Black-Scholes-Merton models of option pricing. We present fast parallel discrete-time finite-difference algorithms for American call option pricing under the binomial and trinomial models and American put option pricing under the Black-Scholes-Merton model. For $T$-step finite differences, each algorithm runs in $O(\left(T\log^2{T}\right)/p + T)$ time under a greedy scheduler on $p$ processing cores, which is a significant improvement over the $\Theta({T^2}/{p}) + \Omega(T\log{T})$ time taken by the corresponding state-of-the-art parallel algorithm. Even when run on a single core, the $O(T\log^2{T})$ time taken by our algorithms is asymptotically much smaller than the $\Theta(T^2)$ running time of the fastest known serial algorithms. Implementations of our algorithms significantly outperform the fastest implementations of existing algorithms in practice, e.g., when run for $T \approx 1000$ steps on a 48-core machine, our algorithm for the binomial model runs at least $15\times$ faster than the fastest existing parallel program for the same model with the speed-up factor gradually reaching beyond $500\times$ for $T \approx 0.5 \times 10^6$. It saves more than 80\% energy when $T \approx 4000$, and more than 99\% energy for $T > 60,000$. Our option pricing algorithms can be viewed as solving a class of nonlinear 1D stencil (i.e., finite-difference) computation problems efficiently using the Fast Fourier Transform (FFT). To our knowledge, ours are the first algorithms to handle such stencils in $o(T^2)$ time. These contributions are of independent interest as stencil computations have a wide range of applications beyond quantitative finance.

Suggested Citation

  • Zafar Ahmad & Reilly Browne & Rezaul Chowdhury & Rathish Das & Yushen Huang & Yimin Zhu, 2023. "Fast American Option Pricing using Nonlinear Stencils," Papers 2303.02317, arXiv.org, revised Oct 2023.
  • Handle: RePEc:arx:papers:2303.02317
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/2303.02317
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Dilip B. Madan & Peter P. Carr & Eric C. Chang, 1998. "The Variance Gamma Process and Option Pricing," Review of Finance, European Finance Association, vol. 2(1), pages 79-105.
    2. Galai, Dan & Masulis, Ronald W., 1976. "The option pricing model and the risk factor of stock," Journal of Financial Economics, Elsevier, vol. 3(1-2), pages 53-81.
    3. Stein, Elias M & Stein, Jeremy C, 1991. "Stock Price Distributions with Stochastic Volatility: An Analytic Approach," The Review of Financial Studies, Society for Financial Studies, vol. 4(4), pages 727-752.
    4. Pinelis, Iosif, 2015. "Characteristic function of the positive part of a random variable and related results, with applications," Statistics & Probability Letters, Elsevier, vol. 106(C), pages 281-286.
    5. Robert C. Merton, 2005. "Theory of rational option pricing," World Scientific Book Chapters, in: Sudipto Bhattacharya & George M Constantinides (ed.), Theory Of Valuation, chapter 8, pages 229-288, World Scientific Publishing Co. Pte. Ltd..
    6. Ibáñez, Alfredo & Zapatero, Fernando, 2004. "Monte Carlo Valuation of American Options through Computation of the Optimal Exercise Frontier," Journal of Financial and Quantitative Analysis, Cambridge University Press, vol. 39(2), pages 253-275, June.
    7. Bakshi, Gurdip & Madan, Dilip, 2000. "Spanning and derivative-security valuation," Journal of Financial Economics, Elsevier, vol. 55(2), pages 205-238, February.
    8. Merton, Robert C., 1976. "Option pricing when underlying stock returns are discontinuous," Journal of Financial Economics, Elsevier, vol. 3(1-2), pages 125-144.
    9. Ball, Clifford A. & Roma, Antonio, 1994. "Stochastic Volatility Option Pricing," Journal of Financial and Quantitative Analysis, Cambridge University Press, vol. 29(4), pages 589-607, December.
    10. Jin-Chuan Duan & Jean-Guy Simonato, 1998. "Empirical Martingale Simulation for Asset Prices," Management Science, INFORMS, vol. 44(9), pages 1218-1233, September.
    11. Boyle, Phelim P., 1977. "Options: A Monte Carlo approach," Journal of Financial Economics, Elsevier, vol. 4(3), pages 323-338, May.
    12. Emanuel Derman & Iraj Kani, 1998. "Stochastic Implied Trees: Arbitrage Pricing with Stochastic Term and Strike Structure of Volatility," International Journal of Theoretical and Applied Finance (IJTAF), World Scientific Publishing Co. Pte. Ltd., vol. 1(01), pages 61-110.
    13. Longstaff, Francis A & Schwartz, Eduardo S, 2001. "Valuing American Options by Simulation: A Simple Least-Squares Approach," University of California at Los Angeles, Anderson Graduate School of Management qt43n1k4jb, Anderson Graduate School of Management, UCLA.
    14. Longstaff, Francis A & Schwartz, Eduardo S, 2001. "Valuing American Options by Simulation: A Simple Least-Squares Approach," The Review of Financial Studies, Society for Financial Studies, vol. 14(1), pages 113-147.
    15. S. G. Kou, 2002. "A Jump-Diffusion Model for Option Pricing," Management Science, INFORMS, vol. 48(8), pages 1086-1101, August.
    16. Ghada Alobaidi & Roland Mallier, 2001. "Asymptotic analysis of American call options," International Journal of Mathematics and Mathematical Sciences, Hindawi, vol. 27, pages 1-12, January.
    17. Oleksandr Zhylyevskyy, 2010. "A fast Fourier transform technique for pricing American options under stochastic volatility," Review of Derivatives Research, Springer, vol. 13(1), pages 1-24, April.
    18. Darrell Duffie & Jun Pan & Kenneth Singleton, 2000. "Transform Analysis and Asset Pricing for Affine Jump-Diffusions," Econometrica, Econometric Society, vol. 68(6), pages 1343-1376, November.
    19. Heston, Steven L, 1993. "A Closed-Form Solution for Options with Stochastic Volatility with Applications to Bond and Currency Options," The Review of Financial Studies, Society for Financial Studies, vol. 6(2), pages 327-343.
    20. Song-Ping Zhu & Zhi-Wei He, 2007. "Calculating The Early Exercise Boundary Of American Put Options With An Approximation Formula," International Journal of Theoretical and Applied Finance (IJTAF), World Scientific Publishing Co. Pte. Ltd., vol. 10(07), pages 1203-1227.
    21. Rama Cont & Ekaterina Voltchkova, 2005. "A Finite Difference Scheme for Option Pricing in Jump Diffusion and Exponential Lévy Models," Post-Print halshs-00445645, HAL.
    22. Chuang‐Chang Chang & San‐Lin Chung & Richard C. Stapleton, 2007. "Richardson extrapolation techniques for the pricing of American‐style options," Journal of Futures Markets, John Wiley & Sons, Ltd., vol. 27(8), pages 791-817, August.
    23. Song-Ping Zhu, 2006. "A New Analytical Approximation Formula For The Optimal Exercise Boundary Of American Put Options," International Journal of Theoretical and Applied Finance (IJTAF), World Scientific Publishing Co. Pte. Ltd., vol. 9(07), pages 1141-1177.
    24. Black, Fischer & Scholes, Myron S, 1973. "The Pricing of Options and Corporate Liabilities," Journal of Political Economy, University of Chicago Press, vol. 81(3), pages 637-654, May-June.
    25. Rendleman, Richard J, Jr & Bartter, Brit J, 1979. "Two-State Option Pricing," Journal of Finance, American Finance Association, vol. 34(5), pages 1093-1110, December.
    26. Cox, John C. & Ross, Stephen A. & Rubinstein, Mark, 1979. "Option pricing: A simplified approach," Journal of Financial Economics, Elsevier, vol. 7(3), pages 229-263, September.
    27. Ockendon, John & Howison, Sam & Lacey, Andrew & Movchan, Alexander, 2003. "Applied Partial Differential Equations," OUP Catalogue, Oxford University Press, number 9780198527718.
    28. Smith, Clifford Jr., 1976. "Option pricing : A review," Journal of Financial Economics, Elsevier, vol. 3(1-2), pages 3-51.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Mark Broadie & Jerome B. Detemple, 2004. "ANNIVERSARY ARTICLE: Option Pricing: Valuation Models and Applications," Management Science, INFORMS, vol. 50(9), pages 1145-1177, September.
    2. Chan, Tat Lung (Ron), 2019. "Efficient computation of european option prices and their sensitivities with the complex fourier series method," The North American Journal of Economics and Finance, Elsevier, vol. 50(C).
    3. Minqiang Li, 2010. "A quasi-analytical interpolation method for pricing American options under general multi-dimensional diffusion processes," Review of Derivatives Research, Springer, vol. 13(2), pages 177-217, July.
    4. Li, Chenxu & Ye, Yongxin, 2019. "Pricing and Exercising American Options: an Asymptotic Expansion Approach," Journal of Economic Dynamics and Control, Elsevier, vol. 107(C), pages 1-1.
    5. Chen, Ding & Härkönen, Hannu J. & Newton, David P., 2014. "Advancing the universality of quadrature methods to any underlying process for option pricing," Journal of Financial Economics, Elsevier, vol. 114(3), pages 600-612.
    6. Blessing Taruvinga & Boda Kang & Christina Sklibosios Nikitopoulos, 2018. "Pricing American Options with Jumps in Asset and Volatility," Research Paper Series 394, Quantitative Finance Research Centre, University of Technology, Sydney.
    7. Kirkby, J. Lars & Nguyen, Duy & Cui, Zhenyu, 2017. "A unified approach to Bermudan and barrier options under stochastic volatility models with jumps," Journal of Economic Dynamics and Control, Elsevier, vol. 80(C), pages 75-100.
    8. Philipp N. Baecker, 2007. "Real Options and Intellectual Property," Lecture Notes in Economics and Mathematical Systems, Springer, number 978-3-540-48264-2, October.
    9. Ravi Kashyap, 2022. "Options as Silver Bullets: Valuation of Term Loans, Inventory Management, Emissions Trading and Insurance Risk Mitigation using Option Theory," Annals of Operations Research, Springer, vol. 315(2), pages 1175-1215, August.
    10. Zura Kakushadze, 2016. "Volatility Smile as Relativistic Effect," Papers 1610.02456, arXiv.org, revised Feb 2017.
    11. Lim, Terence & Lo, Andrew W. & Merton, Robert C. & Scholes, Myron S., 2006. "The Derivatives Sourcebook," Foundations and Trends(R) in Finance, now publishers, vol. 1(5–6), pages 365-572, April.
    12. Duy Nguyen, 2018. "A hybrid Markov chain-tree valuation framework for stochastic volatility jump diffusion models," International Journal of Financial Engineering (IJFE), World Scientific Publishing Co. Pte. Ltd., vol. 5(04), pages 1-30, December.
    13. Antonio Cosma & Stefano Galluccio & Paola Pederzoli & O. Scaillet, 2012. "Valuing American Options Using Fast Recursive Projections," Swiss Finance Institute Research Paper Series 12-26, Swiss Finance Institute.
    14. Duffie, Darrell, 2003. "Intertemporal asset pricing theory," Handbook of the Economics of Finance, in: G.M. Constantinides & M. Harris & R. M. Stulz (ed.), Handbook of the Economics of Finance, edition 1, volume 1, chapter 11, pages 639-742, Elsevier.
    15. Ascione, Giacomo & Mehrdoust, Farshid & Orlando, Giuseppe & Samimi, Oldouz, 2023. "Foreign Exchange Options on Heston-CIR Model Under Lévy Process Framework," Applied Mathematics and Computation, Elsevier, vol. 446(C).
    16. Katarzyna Toporek, 2012. "Simple is better. Empirical comparison of American option valuation methods," Ekonomia journal, Faculty of Economic Sciences, University of Warsaw, vol. 29.
    17. Ravi Kashyap, 2016. "Options as Silver Bullets: Valuation of Term Loans, Inventory Management, Emissions Trading and Insurance Risk Mitigation using Option Theory," Papers 1609.01274, arXiv.org, revised Mar 2022.
    18. Li, Hongshan & Huang, Zhongyi, 2020. "An iterative splitting method for pricing European options under the Heston model☆," Applied Mathematics and Computation, Elsevier, vol. 387(C).
    19. Hongshan Li & Zhongyi Huang, 2020. "An iterative splitting method for pricing European options under the Heston model," Papers 2003.12934, arXiv.org.
    20. Cui, Zhenyu & Lars Kirkby, J. & Nguyen, Duy, 2019. "A general framework for time-changed Markov processes and applications," European Journal of Operational Research, Elsevier, vol. 273(2), pages 785-800.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:arx:papers:2303.02317. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.