Hostname: page-component-78c5997874-v9fdk Total loading time: 0 Render date: 2024-11-05T13:43:45.292Z Has data issue: false hasContentIssue false
  • English
  • Français

QUASI-MONTE CARLO METHODS FOR HIGH-DIMENSIONAL INTEGRATION: THE STANDARD (WEIGHTED HILBERT SPACE) SETTING AND BEYOND

Part of: Numerical approximation and computational geometry

Published online by Cambridge University Press:  29 May 2012

F. Y. KUO ,
CH. SCHWAB  and
I. H. SLOAN
F. Y. KUO
Affiliation:
School of Mathematics and Statistics, University of New South Wales, Sydney NSW 2052, Australia (email: [email protected], [email protected])
CH. SCHWAB
Affiliation:
Seminar for Applied Mathematics, ETH Zürich, ETH Zentrum, HG G57.1, CH8092 Zürich, Switzerland (email: [email protected])
I. H. SLOAN*
Affiliation:
School of Mathematics and Statistics, University of New South Wales, Sydney NSW 2052, Australia (email: [email protected], [email protected])
*
✉For correspondence; e-mail: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

This paper is a contemporary review of quasi-Monte Carlo (QMC) methods, that is, equal-weight rules for the approximate evaluation of high-dimensional integrals over the unit cube [0,1]s. It first introduces the by-now standard setting of weighted Hilbert spaces of functions with square-integrable mixed first derivatives, and then indicates alternative settings, such as non-Hilbert spaces, that can sometimes be more suitable. Original contributions include the extension of the fast component-by-component (CBC) construction of lattice rules that achieve the optimal convergence order (a rate of almost 1/N, where N is the number of points, independently of dimension) to so-called “product and order dependent” (POD) weights, as seen in some recent applications. Although the paper has a strong focus on lattice rules, the function space settings are applicable to all QMC methods. Furthermore, the error analysis and construction of lattice rules can be adapted to polynomial lattice rules from the family of digital nets.

Keywords

quasi-Monte Carlo methodsQMChigh-dimensional integrationweighted spacesreproducing kernel Hilbert spacesBanach space settingsworst-case errordiscrepancyweighted Koksma–Hlawka inequalitylattice ruleslow-discrepancy sequencesfast CBC constructionPOD weights

MSC classification

Secondary: 65D30: Numerical integration
Type
Research Article
Information
The ANZIAM Journal , Volume 53 , Issue 1 , July 2011 , pp. 1 - 37
Copyright
Copyright © Australian Mathematical Society 2012

References

[1]Aronszajn, N., “Theory of reproducing kernels”, Trans. Amer. Math. Soc. 68 (1950) 337–404; doi:10.2307/1990404.CrossRefGoogle Scholar
[2]Bellman, R., Dynamic programming (Princeton University Press, Princeton, 1957).Google ScholarPubMed
[3]Caflisch, R. E., Morokoff, W. and Owen, A., “Valuation of mortgage backed securities using Brownian bridges to reduce effective dimension”, J. Comput. Finance 1 (1997) 27–46.CrossRefGoogle Scholar
[4]Cools, R., Kuo, F. Y. and Nuyens, D., “Constructing embedded lattice rules for multivariate integration”, SIAM J. Sci. Comput. 28 (2006) 2162–2188; doi:10.1137/06065074X.CrossRefGoogle Scholar
[5]Dick, J., “On the convergence rate of the component-by-component construction of good lattice rules”, J. Complexity 20 (2004) 493–522; doi:10.1016/j.jco.2003.11.008.CrossRefGoogle Scholar
[6]Dick, J. and Pillichshammer, F., Digital nets and sequences (Cambridge University Press, Cambridge, 2010).CrossRefGoogle Scholar
[7]Dick, J., Pillichshammer, F. and Waterhouse, B. J., “The construction of good extensible rank-1 lattices”, Math. Comp. 77 (2008) 2345–2374; doi:10.1090/S0025-5718-08-02009-7.CrossRefGoogle Scholar
[8]Faure, H., “Discrépance de suites associées à un système de numération (en dimension s)”, Acta Arith. 41 (1982) 337–351.Google Scholar
[9]Giles, M., Kuo, F. Y., Sloan, I. H. and Waterhouse, B. J., “Quasi-Monte Carlo for finance applications”, ANZIAM J. 50 (2008) C308–C323 (Proc. CTAC 2008).CrossRefGoogle Scholar
[10]Gnewuch, M., “Infinite-dimensional integration on weighted Hilbert spaces”, Math. Comp. in press; doi:10.1090/S0025-5718-2012-02583-X.Google Scholar
[11]Halton, J. H., “On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals”, Numer. Math. 2 (1960) 84–90; doi:10.1007/BF01386213.CrossRefGoogle Scholar
[12]Heinrich, S., Woźniakowski, H., Wasilkowski, G. W. and Novak, E., “The inverse of the star-discrepancy depends linearly on the dimension”, Acta Arith. 96 (2001) 279–302; doi:10.4064/aa96-3-7.CrossRefGoogle Scholar
[13]Hickernell, F. J., “A generalized discrepancy and quadrature error bound”, Math. Comp. 67 (1998) 299–322; doi:10.1090/S0025-5718-98-00894-1.CrossRefGoogle Scholar
[14]Hickernell, F. J., “Lattice rules: How well do they measure up?”, in: Random and quasi-random point sets (eds Hellekalek, P. and Larcher, G.), (Springer, Berlin, 1998) 109–166.CrossRefGoogle Scholar
[15]Hickernell, F. J., Müller-Gronbach, T., Niu, B. and Ritter, K., “Multi-level Monte Carlo algorithms for infinite-dimensional integration on ℝℕ”, J. Complexity 26 (2010) 229–254; doi:10.1016/j.jco.2010.02.002.Google Scholar
[16]Hickernell, F. J., Sloan, I. H. and Wasilkowski, G. W., “On strong tractability of weighted multivariate integration”, Math. Comp. 73 (2004) 1903–1911; doi:10.1090/S0025-5718-04-01653-9.Google Scholar
[17]Hickernell, F. J., Sloan, I. H. and Wasilkowski, G. W., “On tractability of weighted integration for certain Banach spaces of functions”, in: Monte Carlo and quasi-Monte Carlo methods 2002 (ed. Niederreiter, H.), (Springer, Berlin, 2004) 51–71.CrossRefGoogle Scholar
[18]Hickernell, F. J., Sloan, I. H. and Wasilkowski, G. W., “On tractability of weighted integration over bounded and unbounded regions in ℝs”, Math. Comp. 73 (2004) 1885–1901; doi:10.1090/S0025-5718-04-01624-2.CrossRefGoogle Scholar
[19]Hickernell, F. J., Sloan, I. H. and Wasilkowski, G. W., “The strong tractability of multivariate integration using lattice rules”, in: Monte Carlo and quasi-Monte Carlo methods 2002 (ed. Niederreiter, H.), (Springer, Berlin, 2004) 259–273.Google Scholar
[20]Hickernell, F. J. and Wang, X., “The error bounds and tractability of quasi-Monte Carlo algorithms in infinite dimension”, Math. Comp. 71 (2002) 1641–1661; doi:10.1090/S0025-5718-01-01377-1.CrossRefGoogle Scholar
[21]Hickernell, F. J. and Woźniakowski, H., “Integration and approximation in arbitrary dimensions”, Adv. Comput. Math. 12 (2000) 25–58; doi:10.1023/A:1018948631251.CrossRefGoogle Scholar
[22]Hinrichs, A., Pillichshammer, F. and Schmid, W. Ch., “Tractability properties of the weighted star discrepancy”, J. Complexity 24 (2008) 134–143; doi:10.1016/j.jco.2007.08.002.CrossRefGoogle Scholar
[23]Hlawka, E., “Funktionen von beschränkter Variation in der Theorie der Gleichverteilung”, Ann. Mat. Pura Appl. (4) 54 (1961) 325–333; doi:10.1007/BF02415361.CrossRefGoogle Scholar
[24]Hlawka, E., “Über die Diskrepanz mehrdimensionaler Folgen mod. 1”, Math. Z. 77 (1961) 273–284; doi:10.1007/BF01180179.Google Scholar
[25]Joe, S., “Formulas for the computation of the weighted L 2 discrepancy”, Research Report No. 55, Department of Mathematics, University of Waikato, 1997.Google Scholar
[26]Joe, S., “Construction of good rank-1 lattice rules based on the weighted star discrepancy”, in: Monte Carlo and quasi-Monte Carlo methods 2004 (eds Niederreiter, H. and Talay, D.), (Springer, Berlin, 2006) 181–196.CrossRefGoogle Scholar
[27]Joe, S. and Kuo, F. Y., “Constructing Sobol′ sequences with better two-dimensional projections”, SIAM J. Sci. Comput. 30 (2008) 2635–2654; doi:10.1137/070709359.Google Scholar
[28]Koksma, J. F., “Een algemeene stelling uit de theorie der gelijkmatige verdeeling modulo 1”, Mathematica B (Zutphen) 11 (1942/43) 7–11.Google Scholar
[29]Korobov, N. M., Teoretiko-chislovye metody v priblizhennom analize (Gosudarstv. Izdat. Fiz. Mat. Lit., Moscow, 1963) Russian (Number-theoretic methods in approximate analysis).Google Scholar
[30]Kuo, F. Y., “Component-by-component constructions achieve the optimal rate of convergence in weighted Korobov and Sobolev spaces”, J. Complexity 19 (2003) 301–320; doi:10.1016/S0885-064X(03)00006-2.Google Scholar
[31]Kuo, F. Y., Schwab, Ch. and Sloan, I. H., “Quasi-Monte Carlo finite element methods for a class of elliptic partial differential equations with random coefficients”, Research Report 2011-52, Seminar for Applied Mathematics, ETH Zürich, 2011, http://www.sam.math.ethz.ch/reports/2011/52.Google Scholar
[32]Kuo, F. Y., Sloan, I. H., Wasilkowski, G. W. and Waterhouse, B. J., “Randomly shifted lattice rules with the optimal rate of convergence for unbounded integrands”, J. Complexity 26 (2010) 135–160; doi:10.1016/j.jco.2009.07.005.Google Scholar
[33]Kuo, F. Y., Sloan, I. H., Wasilkowski, G. W. and Woźniakowski, H., “On decompositions of multivariate functions”, Math. Comp. 79 (2010) 953–966; doi:10.1090/S0025-5718-09-02319-9.CrossRefGoogle Scholar
[34]Kuo, F. Y., Sloan, I. H., Wasilkowski, G. W. and Woźniakowski, H., “Liberating the dimension”, J. Complexity 26 (2010) 422–454; doi:10.1016/j.jco.2009.12.003.CrossRefGoogle Scholar
[35]Niederreiter, H., “Low-discrepancy and low-dispersion sequences”, J. Number Theory 30 (1988) 51–70; doi:10.1016/0022-314X(88)90025-X.CrossRefGoogle Scholar
[36]Niederreiter, H., Random number generation and quasi-Monte Carlo methods (SIAM, Philadelphia, 1992).Google Scholar
[37]Niederreiter, H. and Xing, C., “Low-discrepancy sequences and global function fields with many rational places”, Finite Fields Appl. 2 (1996) 241–273; doi:10.1006/ffta.1996.0016.Google Scholar
[38]Niu, B., Hickernell, F. J., Müller-Gronbach, T. and Ritter, K., “Deterministic multi-level algorithms for infinite-dimensional integration on ℝℕ”, J. Complexity 27 (2011) 331–351; doi:10.1016/j.jco.2010.08.001.Google Scholar
[39]Novak, E. and Woźniakowski, H., “Intractability results for integration and discrepancy”, J. Complexity 17 (2001) 388–441; doi:10.1006/jcom.2000.0577.CrossRefGoogle Scholar
[40]Novak, E. and Woźniakowski, H., Tractability of multivariate problems. Volume I: Linear information, Volume 6 of EMS Tracts in Mathematics (European Mathematical Society, Zürich, 2008).Google Scholar
[41]Novak, E. and Woźniakowski, H., Tractability of multivariate problems. Volume II: Standard information for functionals, Volume 12 of EMS Tracts in Mathematics (European Mathematical Society, Zürich, 2010).CrossRefGoogle Scholar
[42]Nuyens, D. and Cools, R., “Fast algorithms for component-by-component construction of rank 1 lattice rules in shift-invariant reproducing kernel Hilbert spaces”, Math. Comp. 75 (2006) 903–920; doi:10.1090/S0025-5718-06-01785-6.CrossRefGoogle Scholar
[43]Nuyens, D. and Cools, R., “Fast component-by-component construction of rank-1 lattice rules with a nonprime number of points”, J. Complexity 22 (2006) 4–28; doi:10.1016/j.jco.2005.07.002.CrossRefGoogle Scholar
[44]Plaskota, L. and Wasilkowski, G. W., “Tractability of infinite-dimensional integration in the worst case and randomized settings”, J. Complexity 27 (2001) 505–518; doi:10.1016/j.jco.2011.01.006.CrossRefGoogle Scholar
[45]Sinescu, V. and Joe, S., “Good lattice rules based on the general weighted star discrepancy”, Math. Comp. 76 (2007) 989–1004; doi:10.1090/S0025-5718-06-01943-0.CrossRefGoogle Scholar
[46]Sinescu, V. and Joe, S., “Good lattice rules with a composite number of points based on the product weighted star discrepancy”, in: Monte Carlo and quasi-Monte Carlo methods 2006 (eds Keller, A., Heinrich, S. and Niederreiter, H.), (Springer, Berlin, 2008) 645–658.CrossRefGoogle Scholar
[47]Sinescu, V. and L’Ecuyer, P., “Existence and construction of shifted lattice rules with an arbitrary number of points and bounded weighted star discrepancy for general decreasing weights”, J. Complexity 27 (2011) 449–465; doi:10.1016/j.jco.2011.02.001.Google Scholar
[48]Sloan, I. H. and Joe, S., Lattice methods for multiple integration (Oxford University Press, Oxford, 1994).CrossRefGoogle Scholar
[49]Sloan, I. H., Kuo, F. Y. and Joe, S., “On the step-by-step construction of quasi-Monte Carlo integration rules that achieve strong tractability error bounds in weighted Sobolev spaces”, Math. Comp. 71 (2002) 1609–1640; doi:10.1090/S0025-5718-02-01420-5.CrossRefGoogle Scholar
[50]Sloan, I. H., Kuo, F. Y. and Joe, S., “Constructing randomly shifted lattice rules in weighted Sobolev spaces”, SIAM J. Numer. Anal. 40 (2002) 1650–1665; doi:10.1137/S0036142901393942.Google Scholar
[51]Sloan, I. H. and Reztsov, A. V., “Component-by-component construction of good lattice rules”, Math. Comp. 71 (2002) 263–273; doi:10.1090/S0025-5718-01-01342-4.Google Scholar
[52]Sloan, I. H., Wang, X. and Woźniakowski, H., “Finite-order weights imply tractability of multivariate integration”, J. Complexity 20 (2004) 46–74; doi:10.1016/j.jco.2003.11.003.CrossRefGoogle Scholar
[53]Sloan, I. H. and Woźniakowski, H., “When are quasi-Monte Carlo algorithms efficient for high-dimensional integrals?”, J. Complexity 14 (1998) 1–33; doi:10.1006/jcom.1997.0463.CrossRefGoogle Scholar
[54]Sloan, I. H. and Woźniakowski, H., “Tractability of multivariate integration for weighted Korobov classes”, J. Complexity 17 (2001) 697–721; doi:10.1006/jcom.2001.0599.Google Scholar
[55]Sobol′, I. M., “On the distribution of points in a cube and the approximate evaluation of integrals”, Zh. Vȳchisl. Mat. Mat. Fiz. 7 (1967) 784–802. English translation: U.S.S.R. Comput. Math. Math. Phys. 7 (1967) 86–112; doi:10.1016/0041-5553(67)90144-9.Google Scholar
[56]Sobol′, I. M., Multidimensional quadrature formulas and Haar functions (Nauka, Moscow, 1969).Google Scholar
[57]Sobol′, I. M., “Sensitivity estimates for nonlinear mathematical models”, Matematicheskoe Modelirovanie 2 (1990) 112–118; English translation: Math. Model. Comput. Experiment 1 (1993) 407–414.Google Scholar
[58]Stroud, A. H., Approximate calculation of multiple integrals (Prentice-Hall, Englewood Cliffs, NJ, 1971).Google Scholar
[59]Wang, X., “Strong tractability of multivariate integration using quasi-Monte Carlo algorithms”, Math. Comp. 72 (2003) 823–838; doi:10.1090/S0025-5718-02-01440-0.CrossRefGoogle Scholar
[60]Warnock, T. T., “Computational investigations of low-discrepancy point sets”, in: Applications of number theory to numerical analysis (ed. Zaremba, S. K.), (Academic Press, New York, 1972) 319–343.CrossRefGoogle Scholar
[61]Zaremba, S. K., “Some applications of multidimensional integration by parts”, Ann. Polon. Math. 21 (1968) 85–96.CrossRefGoogle Scholar