An Efficient Quasi-Monte Carlo Algorithm for High Dimensional Numerical Integration

Huicong Zhong

doi:10.3390/math13213437

2025-10-28

PRE

Huicong Zhong

Xiaobing Feng *

DOI：10.3390/math13213437

原文链接

原文求助

摘要

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.

Keyword:

lattice rule (LR)

multilevel dimension iteration (MDI)

Monte Carlo (MC) and Quasi-Monte Carlo (QMC) methods

high dimensional integration