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

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.