Abstract
Quasi-Monte Carlo methods are used for numerically integrating multivariate functions. However, the error bounds for these methods typically rely on a priori knowledge of some semi-norm of the integrand, not on the sampled function values. In this article, we propose an error bound based on the discrete Fourier coefficients of the integrand. If these Fourier coefficients decay more quickly, the integrand has less fine scale structure, and the accuracy is higher. We focus on rank-1 lattices because they are a commonly used quasi-Monte Carlo design and because their algebraic structure facilitates an error analysis based on a Fourier decomposition of the integrand. This leads to a guaranteed adaptive cubature algorithm with computational cost \(\mathscr {O}(mb^m)\), where b is some fixed prime number and \(b^m\) is the number of data points.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Choi, S.C.T., Ding, Y., Hickernell, F.J., Jiang, L., Jiménez Rugama, Ll.A., Tong, X., Zhang, Y., Zhou, X.: GAIL: Guaranteed Automatic Integration Library (versions 1.0–2.1). MATLAB software. https://github.com/GailGithub/GAIL_Dev (2013–2015)
Clancy, N., Ding, Y., Hamilton, C., Hickernell, F.J., Zhang, Y.: The cost of deterministic, adaptive, automatic algorithms: cones, not balls. J. Complex. 30(1), 21–45 (2014)
Dick, J., Kuo, F., Sloan, I.H.: High dimensional integration – the Quasi-Monte Carlo way. Acta Numer. 22, 133–288 (2013)
Hickernell, F.J.: Obtaining \(O(N^{-2+\epsilon })\) convergence for lattice quadrature rules. In: Fang, K.T., Hickernell, F.J., Niederreiter, H. (eds.) Monte Carlo and Quasi-Monte Carlo Methods 2000, pp. 274–289. Springer, Berlin (2002)
Hickernell, F.J., Jiménez Rugama, Ll.A.: Reliable adaptive cubature using digital sequences. In: Cools, R., Nuyens, D., (eds.) Monte Carlo and Quasi-Monte Carlo Methods 2014, vol. 163, pp. 367–383. Springer, Heidelberg (2016)
Hickernell, F.J., Niederreiter, H.: The existence of good extensible rank-1 lattices. J. Complex. 19, 286–300 (2003)
Hickernell, F.J., Sloan, I.H., Wasilkowski, G.W.: On tractability of weighted integration over bounded and unbounded regions in \(\mathbb{R}^s\). Math. Comput. 73, 1885–1901 (2004)
Hickernell, F.J., Sloan, I.H., Wasilkowski, G.W.: The strong tractability of multivariate integration using lattice rules. In: Niederreiter, H. (ed.) Monte Carlo and Quasi-Monte Carlo Methods 2002, pp. 259–273. Springer, Berlin (2004)
L’Ecuyer, P., Munger, D.: Algorithm xxx: A general software tool for constructing rank-1 lattice rules. ACM Trans. Math. Softw. (2016). To appear, http://www.iro.umontreal.ca/~lecuyer/myftp/papers/latbuilder.pdf
Niederreiter, H.: Random Number Generation and Quasi-Monte Carlo Methods. CBMS-NSF Regional Conference Series in Applied Mathematics. SIAM, Philadelphia (1992)
Novak, E., Woźniakowski, H.: Tractability of Multivariate Problems Volume II: Standard Information for Functionals. No. 12 in EMS Tracts in Mathematics. European Mathematical Society, Zürich (2010)
Sidi, A.: A new variable transformation for numerical integration. In: Brass, H., Hämmerlin, G. (eds.) Numerical Integration IV, No. 112 in International Series of Numerical Mathematics, pp. 359–373. Birkhäuser, Basel (1993)
Sloan, I.H., Joe, S.: Lattice Methods for Multiple Integration. Oxford University Press, Oxford (1994)
Acknowledgments
The authors thank Ronald Cools and Dirk Nuyens for organizing MCQMC 2014 and greatly appreciate the suggestions made by Sou-Cheng Choi, Frances Kuo, Lan Jiang, Dirk Nuyens and Yizhi Zhang to improve this manuscript. In addition, the first author also thanks Art B. Owen for partially funding traveling expenses to MCQMC 2014 through the US National Science Foundation (NSF). This work was partially supported by NSF grants DMS-1115392, DMS-1357690, and DMS-1522687.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Jiménez Rugama, L.A., Hickernell, F.J. (2016). Adaptive Multidimensional Integration Based on Rank-1 Lattices. In: Cools, R., Nuyens, D. (eds) Monte Carlo and Quasi-Monte Carlo Methods. Springer Proceedings in Mathematics & Statistics, vol 163. Springer, Cham. https://doi.org/10.1007/978-3-319-33507-0_20
Download citation
DOI: https://doi.org/10.1007/978-3-319-33507-0_20
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-33505-6
Online ISBN: 978-3-319-33507-0
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)