×

zbMATH — the first resource for mathematics

Efficient calculation of the worst-case error and (fast) component-by-component construction of higher order polynomial lattice rules. (English) Zbl 1244.65002
An important problem in the theory of quasi-Monte Carlo integration is the consideration of functional spaces, and the construction of well distributed \(s\)-dimensional nets, which are to be the nodes of the integration, and to provide an optimal order of the worst-case error.
In the present paper the authors introduce the functional space \({\mathcal W}_{\alpha, s, \gamma},\) which forms a Korobov space. This functional space contains functions with certain decay rate of their Fourier-Walsh coefficients. The concept of the so-called higher order polynomial lattice point sets is given, and these sets are used in the practice of quasi-Monte Carlo integration in the space \({\mathcal W}_{\alpha, s, \gamma}.\)
In the introduction of the article, the main ideas of quasi-Monte Carlo rules are reminded. Some constructive principles of \(b\)-adic digital nets are discussed. The order of the worst-case error of the integration in some functional classes is considered.
In Section 2 some preliminary natations, related with using Walsh functions in base \(b,\) are presented. The concept of the functional space \({\mathcal W}_{\alpha, s, \gamma}\) is developed. In Definition 1 the construction scheme of digital nets is given. In Definition 2 the concept of the dual digital nets is presented. In Definitions 3 and 4 the details of the polynomial lattice rules and their dual polynomial lattice are presented. In Algorithm 1 the component-by-component (CBC) construction of higher order polynomial lattice rules is developed. In Theorem 1 an estimation of the worst-case error of the integration is obtained. It is shown that the sets constructed in Algorithm 1 achieve almost optimal rates of convergence of the worst-case error of the integration in the space \({\mathcal W}_{\alpha, s, \gamma}.\) In Lemma 1 an explicit formula for the worst-case error of the integration in the space \({\mathcal W}_{\alpha, s, \gamma}\) is obtained.
In Section 3 it is shown how to efficiently calculate the worst-case error obtained in Lemma 1, and how the construction of higher order polynomial lattice rules can be done using the fast CBC approach. The worst-case error is analysed. In Algorithm 2 the fast CBC construction of higher order polynomial lattice rules is given.
In Section 4 it is shown how to calculate the infinite sum \(\omega_{\alpha}(x)\) from the formula for the worst-case error. First an explicit formula for the quantity \(\omega_{\alpha}(x)\) is obtained. In Theorem 2 it is shown that, if \(x\) can be represented with \(n\) digits in base \(b,\) then \(\omega_{\alpha}(x)\) can be computed through \({\mathcal O}(\alpha n)\) operations. In Theorem 3 explicit forms of \(\omega_{\alpha}(x)\) for general \(x \in [0,1)\) and small \(\alpha\) are given. Corollary 1 considers the main results of Theorem 3 in the case when \(b=2.\)
In Section 5 the explicit constructions, based on using the CBC algorithm and the fast CBC construction of higher order polynomial lattice rules, are compared. The numerical data in the tests show that the new construction produces better results.

MSC:
65C05 Monte Carlo methods
11K36 Well-distributed sequences and other variations
11K45 Pseudo-random numbers; Monte Carlo methods
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Baldeaux, J., Dick, J.: QMC rules of arbitrary high order: reproducing kernel Hilbert space approach. Constr. Approx. 30(3), 495–527 (2009) · Zbl 1186.65005 · doi:10.1007/s00365-009-9074-y
[2] Baldeaux, J., Dick, J., Greslehner, J., Pillichshammer, F.: Construction algorithms for higher order polynomial lattice rules. J. Complex. 27(3–4), 281–299 (2011) · Zbl 1218.65003 · doi:10.1016/j.jco.2010.06.002
[3] Dick, J.: Higher order scrambled digital nets achieve the optimal rate of the root mean square error for smooth integrands. Ann. Stat. 39(3), 1372–1398 (2011) · Zbl 1298.65011 · doi:10.1214/11-AOS880
[4] Dick, J.: Explicit constructions of quasi-Monte Carlo rules for the numerical integration of high dimensional periodic functions. SIAM J. Numer. Anal. 45, 2141–2176 (2007) · Zbl 1158.65007 · doi:10.1137/060658916
[5] Dick, J.: Walsh spaces containing smooth functions and quasi-Monte Carlo rules of arbitrary high order. SIAM J. Numer. Anal. 46(3), 1519–1553 (2008) · Zbl 1189.42012 · doi:10.1137/060666639
[6] Dick, J.: The decay of the Walsh coefficients of smooth functions. Bull. Aust. Math. Soc. 80, 430–453 (2009) · Zbl 1183.42027 · doi:10.1017/S0004972709000392
[7] Dick, J., Kritzer, P., Pillichshammer, F., Schmid, W.C.: On the existence of higher order polynomial lattices based on a generalized figure of merit. J. Complex. 23(4–6), 581–593 (2007) · Zbl 1130.65047 · doi:10.1016/j.jco.2006.12.003
[8] Dick, J., Kuo, F.Y., Pillichshammer, F., Sloan, I.H.: Construction algorithms for polynomial lattice rules for multivariate integration. Math. Comput. 74(252), 1895–1921 (2005) · Zbl 1079.65007 · doi:10.1090/S0025-5718-05-01742-4
[9] Dick, J., Pillichshammer, F.: Multivariate integration in weighted Hilbert spaces based on Walsh functions and weighted Sobolev spaces. J. Complex. 21(2), 149–195 (2005) · Zbl 1085.41021 · doi:10.1016/j.jco.2004.07.003
[10] Dick, J., Pillichshammer, F.: Strong tractability of multivariate integration of arbitrary high order using digitally shifted polynomial lattice rules. J. Complex. 23(4–6), 436–453 (2007) · Zbl 1130.65005 · doi:10.1016/j.jco.2007.02.001
[11] Dick, J., Pillichshammer, F.: Digital Nets and Sequences: Discrepancy Theory and Quasi-Monte Carlo Integration. Cambridge University Press, Cambridge (2010) · Zbl 1282.65012
[12] Korobov, N.M.: The approximate computation of multiple integrals/approximate evaluation of repeated integrals. Dokl. Akad. Nauk SSSR 124, 1207–1210 (1959) in Russian · Zbl 0089.04201
[13] Korobov, N.M.: Number-Theoretic Methods in Approximate Analysis. Goz. Izdat. Fiz.-Math (1963) in Russian · Zbl 0115.11703
[14] Larcher, G., Lauss, A., Niederreiter, H., Schmid, W.C.: Optimal polynomials for (t, m, s)-nets and numerical integration of multivariate Walsh series. SIAM J. Numer. Anal. 33(6), 2239–2253 (1996) · Zbl 0861.65019 · doi:10.1137/S0036142994264705
[15] Niederreiter, H.: Random Number Generation and Quasi-Monte Carlo Methods, no. 63. Regional Conference Series in Applied Mathematics. SIAM (1992) · Zbl 0761.65002
[16] Novak, E., Woźniakowski, H.: Tractability of Multivariate Problems–vol. I: Linear Information. EMS Tracts in Mathematics, vol. 6. European Mathematical Society Publishing House (2008) · Zbl 1156.65001
[17] Novak, E., Woźniakowski, H.: Tractability of Multivariate Problems–vol. II: Standard Information for Functionals. EMS Tracts in Mathematics, vol. 12. European Mathematical Society Publishing House (2010) · Zbl 1241.65025
[18] Nussbaumer, H.J.: Fast Fourier Transform and Convolution Algorithms, 2nd edn. Springer-Verlag (1982) · Zbl 0476.65097
[19] Nuyens, D.: Fast construction of good lattice rules. Ph.D. Thesis, Dept. of Computer Science, K. U. Leuven (2007) · Zbl 1152.65365
[20] Nuyens, D., Cools, R.: Fast algorithms for component-by-component construction of rank-1 lattice rules in shift-invariant reproducing kernel Hilbert spaces. Math. Comput. 75(254), 903–920 (2006) · Zbl 1094.65004 · doi:10.1090/S0025-5718-06-01785-6
[21] Nuyens, D., Cools, R.: Fast component-by-component construction, a reprise for different kernels. In: Niederreiter, H., Talay, D. (eds.) Monte Carlo and Quasi-Monte Carlo Methods 2004, pp. 371–385. Springer-Verlag (2006) · Zbl 1099.65006
[22] Owen, A.B.: Monte Carlo variance of scrambled net quadrature. SIAM J. Numer. Anal. 34(5), 1884–1910 (1997) · Zbl 0890.65023 · doi:10.1137/S0036142994277468
[23] Pirsic, G.: A software implementation of Niederreiter–Xing sequences. In: Fang, K.T., Hickernell, F.J., Niederreiter, H. (eds.) Monte Carlo and Quasi-Monte Carlo Methods 2000, pp. 434–445. Springer-Verlag (2002) · Zbl 1112.65304
[24] Schmid, W.C.: Improvements and extensions of the ”Salzburg Tables” by using irreducible polynomials. In: Niederreiter, H., Spanier, J. (eds.) Monte Carlo and Quasi-Monte Carlo Methods 1998, pp. 436–447. Springer, Berlin (2000) · Zbl 0963.11040
[25] Sloan, I.H., Reztsov, A.V.: Component-by-component construction of good lattice rules. Math. Comput. 71(237), 263–273 (2002) · Zbl 0985.65018 · doi:10.1090/S0025-5718-01-01342-4
[26] Sloan, I.H., Woźniakowski, H.: When are quasi-Monte Carlo algorithms efficient for high dimensional integrals? J. Complex. 14(1), 1–33 (1998) · Zbl 1032.65011 · doi:10.1006/jcom.1997.0463
[27] Stahnke, W.: Primitive binary polynomials. Math. Comput. 27(124), 977–980 (1973) · Zbl 0279.12007 · doi:10.1090/S0025-5718-1973-0327722-7
[28] Šarygin, I.F.: Lower bounds for the error of quadrature formulas on classes of functions. USSR Comput. Math. Math. Phys. 3, 489–497 (1965); Translation from Russian Zh. Vychisl. Mat. Mat. Fiz. 3, 370–376 (1963) · Zbl 0133.39202 · doi:10.1016/0041-5553(63)90033-8
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.