.png){kind=icon}
.png){kind=icon}
Return
An Efficient Quasi-Monte Carlo Algorithm for High Dimensional Numerical Integration
.png){kind=icon}
PRE
AI
DOI：10.3390/math13213437.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In this paper, we develop a fast numerical algorithm, termed MDI-LR, for the efficient implementation of quasi-Monte Carlo lattice rules in computing d-dimensional integrals of a given function. The algorithm is based on converting the underlying lattice rule into a tensor-product form through an affine transformation, and further improving computational efficiency by incorporating a multilevel dimension iteration (MDI) strategy. This approach computes the function evaluations at the integration points collectively and iterates along each transformed coordinate direction, allowing substantial reuse of computations. As a result, the algorithm avoids the need to explicitly store integration points or compute function values at those points independently. Extensive numerical experiments are conducted to evaluate the performance of MDI-LR and compare it with the straightforward implementation of quasi-Monte Carlo lattice rules. The results demonstrate that MDI-LR achieves a computational complexity of order O(N2d3) or better, where N denotes the number of points in each transformed coordinate direction. Thus, MDI-LR effectively mitigates the curse of dimensionality and revitalizes the use of QMC lattice rules for high dimensional integration.
Keywords:
lattice rule (LR)
multilevel dimension iteration (MDI)
Monte Carlo (MC) and Quasi-Monte Carlo (QMC) methods
high dimensional integration
Journal
IF:
2.2
Papers:
2.9K
Citations:
3.6W