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. 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).
    2. 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.
    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. 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.
    4. Jérôme Detemple, 2014. "Optimal Exercise for Derivative Securities," Annual Review of Financial Economics, Annual Reviews, vol. 6(1), pages 459-487, December.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. Georges Dionne & Geneviève Gauthier & Nadia Ouertani, 2009. "Basket Options on Heterogeneous Underlying Assets," Cahiers de recherche 0918, CIRPEE.
    10. 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.
    11. 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.
    12. Berridge, S.J. & Schumacher, J.M., 2002. "An Irregular Grid Approach for Pricing High Dimensional American Options," Other publications TiSEM 416a6d43-3466-47e0-b656-d, Tilburg University, School of Economics and Management.
    13. Burcu Aydoğan & Ümit Aksoy & Ömür Uğur, 2018. "On the methods of pricing American options: case study," Annals of Operations Research, Springer, vol. 260(1), pages 79-94, January.
    14. Dimitrakopoulos, Roussos G. & Abdel Sabour, Sabry A., 2007. "Evaluating mine plans under uncertainty: Can the real options make a difference?," Resources Policy, Elsevier, vol. 32(3), pages 116-125, September.
    15. Zhu, Lei & Zhang, ZhongXiang & Fan, Ying, 2015. "Overseas oil investment projects under uncertainty: How to make informed decisions?," Journal of Policy Modeling, Elsevier, vol. 37(5), pages 742-762.
    16. Yijuan Liang & Xiuchuan Xu, 2019. "Variance and Dimension Reduction Monte Carlo Method for Pricing European Multi-Asset Options with Stochastic Volatilities," Sustainability, MDPI, vol. 11(3), pages 1-21, February.
    17. Tomáš Tichý, 2008. "Posouzení vybraných možností zefektivnění simulace Monte Carlo při opčním oceňování [Examination of selected improvement approaches to Monte Carlo simulation in option pricing]," Politická ekonomie, Prague University of Economics and Business, vol. 2008(6), pages 772-794.
    18. Berridge, S.J. & Schumacher, J.M., 2004. "Pricing High-Dimensional American Options Using Local Consistency Conditions," Other publications TiSEM 8c8de631-5039-4eec-a965-3, Tilburg University, School of Economics and Management.
    19. Zbigniew Palmowski & Tomasz Serafin, 2020. "Note on simulation pricing of $\pi$-options," Papers 2007.02076, arXiv.org, revised Aug 2020.
    20. Axel Kind, 2005. "Pricing American-Style Options By Simulation," Financial Markets and Portfolio Management, Springer;Swiss Society for Financial Market Research, vol. 19(1), pages 109-116, June.

    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.