IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v11y2023i19p4191-d1254929.html
   My bibliography  Save this article

An Efficient and Fast Sparse Grid Algorithm for High-Dimensional Numerical Integration

Author

Listed:
  • Huicong Zhong

    (School of Mathematics and Statistics, Northwestern Polytechnical University, Xi’an 710129, China
    These authors contributed equally to this work.)

  • Xiaobing Feng

    (Department of Mathematics, The University of Tennessee, Knoxville, TN 37996, USA
    These authors contributed equally to this work.)

Abstract

This paper is concerned with developing an efficient numerical algorithm for the fast implementation of the sparse grid method for computing the d -dimensional integral of a given function. The new algorithm, called the MDI-SG (multilevel dimension iteration sparse grid) method, implements the sparse grid method based on a dimension iteration/reduction procedure. It does not need to store the integration points, nor does it compute the function values independently at each integration point; instead, it reuses the computation for function evaluations as much as possible by performing the function evaluations at all integration points in a cluster and iteratively along coordinate directions. It is shown numerically that the computational complexity (in terms of CPU time) of the proposed MDI-SG method is of polynomial order O ( d 3 N b ) ( b ≤ 2 ) or better, compared to the exponential order O ( N ( log N ) d − 1 ) for the standard sparse grid method, where N denotes the maximum number of integration points in each coordinate direction. As a result, the proposed MDI-SG method effectively circumvents the curse of dimensionality suffered by the standard sparse grid method for high-dimensional numerical integration.

Suggested Citation

  • Huicong Zhong & Xiaobing Feng, 2023. "An Efficient and Fast Sparse Grid Algorithm for High-Dimensional Numerical Integration," Mathematics, MDPI, vol. 11(19), pages 1-26, October.
    • Handle: RePEc:gam:jmathe:v:11:y:2023:i:19:p:4191-:d:1254929
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/11/19/4191/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/11/19/4191/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Maruri-Aguilar, Hugo & Wynn, Henry, 2023. "Sparse polynomial prediction," LSE Research Online Documents on Economics 118748, London School of Economics and Political Science, LSE Library.
    2. Yang, Xuehua & Wu, Lijiao & Zhang, Haixiang, 2023. "A space-time spectral order sinc-collocation method for the fourth-order nonlocal heat model arising in viscoelasticity," Applied Mathematics and Computation, Elsevier, vol. 457(C).
    3. Barraquand, Jérôme & Martineau, Didier, 1995. "Numerical Valuation of High Dimensional Multivariate American Securities," Journal of Financial and Quantitative Analysis, Cambridge University Press, vol. 30(3), pages 383-405, September.
    4. Justin Sirignano & Konstantinos Spiliopoulos, 2017. "DGM: A deep learning algorithm for solving partial differential equations," Papers 1708.07469, arXiv.org, revised Sep 2018.
    5. Jèôme Barraquand, 1995. "Numerical Valuation of High Dimensional Multivariate European Securities," Management Science, INFORMS, vol. 41(12), pages 1882-1891, December.
    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. Sebastian Becker & Patrick Cheridito & Arnulf Jentzen & Timo Welti, 2019. "Solving high-dimensional optimal stopping problems using deep learning," Papers 1908.01602, arXiv.org, revised Aug 2021.
    2. O. Samimi & Z. Mardani & S. Sharafpour & F. Mehrdoust, 2017. "LSM Algorithm for Pricing American Option Under Heston–Hull–White’s Stochastic Volatility Model," Computational Economics, Springer;Society for Computational Economics, vol. 50(2), pages 173-187, August.
    3. Ernst, Philip A. & Rogers, L.C.G. & Zhou, Quan, 2017. "The value of foresight," Stochastic Processes and their Applications, Elsevier, vol. 127(12), pages 3913-3927.
    4. Calypso Herrera & Florian Krach & Pierre Ruyssen & Josef Teichmann, 2021. "Optimal Stopping via Randomized Neural Networks," Papers 2104.13669, arXiv.org, revised Dec 2023.
    5. Anne Laure Bronstein & Gilles Pagès & Jacques Portès, 2013. "Multi-asset American Options and Parallel Quantization," Methodology and Computing in Applied Probability, Springer, vol. 15(3), pages 547-561, September.
    6. Jian Liang & Zhe Xu & Peter Li, 2019. "Deep Learning-Based Least Square Forward-Backward Stochastic Differential Equation Solver for High-Dimensional Derivative Pricing," Papers 1907.10578, arXiv.org, revised Oct 2020.
    7. Jérôme Detemple, 2014. "Optimal Exercise for Derivative Securities," Annual Review of Financial Economics, Annual Reviews, vol. 6(1), pages 459-487, December.
    8. Martzoukos, Spiros H., 2001. "The option on n assets with exchange rate and exercise price risk," Journal of Multinational Financial Management, Elsevier, vol. 11(1), pages 1-15, February.
    9. E Saliby & R J Paul, 2009. "A farewell to the use of antithetic variates in Monte Carlo simulation," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(7), pages 1026-1035, July.
    10. Lars Stentoft, 2004. "Convergence of the Least Squares Monte Carlo Approach to American Option Valuation," Management Science, INFORMS, vol. 50(9), pages 1193-1203, September.
    11. Sebastian Becker & Patrick Cheridito & Arnulf Jentzen, 2020. "Pricing and Hedging American-Style Options with Deep Learning," JRFM, MDPI, vol. 13(7), pages 1-12, July.
    12. Lukito Adi Nugroho, 2017. "Real options valuation of franchise territorial exclusivity," Cogent Business & Management, Taylor & Francis Journals, vol. 4(1), pages 1262490-126, January.
    13. Ivan Guo & Nicolas Langren'e & Jiahao Wu, 2023. "Simultaneous upper and lower bounds of American option prices with hedging via neural networks," Papers 2302.12439, arXiv.org, revised Apr 2024.
    14. Boyle, Phelim & Broadie, Mark & Glasserman, Paul, 1997. "Monte Carlo methods for security pricing," Journal of Economic Dynamics and Control, Elsevier, vol. 21(8-9), pages 1267-1321, June.
    15. Ng, Andrew C.Y. & Li, Johnny Siu-Hang & Chan, Wai-Sum, 2013. "Pricing options on stocks denominated in different currencies: Theory and illustrations," The North American Journal of Economics and Finance, Elsevier, vol. 26(C), pages 339-354.
    16. Rombouts, Jeroen V.K. & Stentoft, Lars, 2011. "Multivariate option pricing with time varying volatility and correlations," Journal of Banking & Finance, Elsevier, vol. 35(9), pages 2267-2281, September.
    17. Berridge, S.J. & Schumacher, J.M., 2002. "An Irregular Grid Approach for Pricing High Dimensional American Options," Discussion Paper 2002-99, Tilburg University, Center for Economic Research.
    18. Georges Dionne & Geneviève Gauthier & Nadia Ouertani, 2009. "Basket Options on Heterogeneous Underlying Assets," Cahiers de recherche 0918, CIRPEE.
    19. Bally Vlad & Caramellino Lucia & Zanette Antonino, 2005. "Pricing and hedging American options by Monte Carlo methods using a Malliavin calculus approach," Monte Carlo Methods and Applications, De Gruyter, vol. 11(2), pages 97-133, June.
    20. Robert H. Keeley & Sanjeev Punjabi & Lassaad Turki, 1996. "Valuation of Early-Stage Ventures: Option Valuation Models vs. Traditional Approaches," Journal of Entrepreneurial Finance, Pepperdine University, Graziadio School of Business and Management, vol. 5(2), pages 115-138, Summer.

    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:gam:jmathe:v:11:y:2023:i:19:p:4191-:d:1254929. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    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.