# zbMATH — the first resource for mathematics

A construction of polynomial lattice rules with small gain coefficients. (English) Zbl 1298.65010
The well-distributed nets and sequences in the $$s$$-dimensional unit cube $$[0,1)^{s}$$ have many applications in different branches of the numerical methods, especially to the theory of quasi-Monte Carlo integration. The so-called digital nets and polynomial lattice rules are important for quasi-Monte Carlo integration.
In the present paper the polynomial lattice rules, which have in some sense, small gain coefficients by using component-by-component (CBC) algorithm are constructed. For approximate calculation of the integral $$\int_{[0,1]^{s}} f ({\mathbf x}) d {\mathbf x},$$ where the integrand $$f$$ belongs to a given functional class, the quasi-Monte Carlo rules $$\hat{I}(f) = {1 \over b^{m}} \sum_{h=0}^{b^{m}-1} f({\mathbf y}_{h}),$$ where the points $$\{{\mathbf y}_{h}\}_{h=0}^{b^{m}-1}$$ are obtained by applying the scrambling algorithm to a polynomial lattice rules, is used. The variance of the estimator $$\hat{I}(f)$$ is investigated. The aim of the paper is to find polynomial lattice rules for which the weighted sum of gain coefficients is minimized.
In Section 2, the polynomial lattice rules are reminded. The scrambling algorithm of Owen is described. The definition of Walsh functions is briefly recalled. The space $${\mathcal F}_{\alpha, s, \gamma}$$ of functions with finite weighted norm is defined. The generalized variation in the sense of Vitali of order $$0 < \alpha \leq 1$$ is defined.
In Section 3, the variance of the estimator $$\hat{I}(f) = {1 \over b^{m}} \sum_{h=0}^{b^{m}-1} f({\mathbf y}_{h}),$$ where the points $$\{{\mathbf y}_{h}\}_{h=0}^{b^{m}-1}$$ are obtained by applying the scrambling algorithm to a digital $$(t, m, s)$$-net over $$\mathbb Z_{b},$$ is investigated. In Corollary 2, an explicit formula for the worst-case variance of the multivariate integration in the space $${\mathcal F}_{\alpha, s, \gamma}$$ using a scrambled quasi-Monte Carlo rule is obtained.
In Section 4, it is shown how to construct a polynomial lattice rule using a CBC approach such that the worst-case variance of the multivariate integration in the space $${\mathcal F}_{\alpha, s, \gamma}$$ converges at a rate of $$N^{-1 - 2 \alpha + \delta},$$ for any $$\delta > 0.$$ In Algorithm 1, the CBC algorithm is described. Theorem 1 shows that Algorithm 1 indeed constructs a generated vector such that the above variance has a rate of $$N^{-1 - 2 \alpha + \delta},$$ for any $$\delta > 0.$$ Corollary 3 shows the tractability of Algorithm 1.
In Section 5, Korobov polynomial lattice rules are constructed. This is made in Algorithm 2. In Theorem 2, an upper estimation of the worst-case variance of the integration in the space $${\mathcal F}_{\alpha, s, \gamma}$$ by using the lattice rules constructed by using Algorithm 2 is obtained. Corollary 4 discusses the tractability of Algorithm 2.
In Section 6, a lower bound of the worst-case variance is obtained. Theorem 3 presents the lower bound of the worst-case variance, which applies the all randomized algorithms.
In Section 7, an implementation of the CBC algorithm is realized. In Algorithm 3, a fast version of CBC is described. In Corollary 5 the time $${\mathcal O}(s b^{m}m)$$ and the memory $${\mathcal O}(b^{m})$$ are obtained.
In Section 8, the performance of the CBC algorithm is numerically investigated. The performance of the CBC algorithm is compared with the performance of digital nets.

##### MSC:
 65C05 Monte Carlo methods 65C10 Random number generation in numerical analysis 65D30 Numerical integration 11K31 Special sequences 11K36 Well-distributed sequences and other variations 11K45 Pseudo-random numbers; Monte Carlo methods
##### Software:
Algorithm 823; sobol.cc; TOMS659
Full Text:
##### References:
  Baldeaux, J.: Higher order nets and sequences, PhD thesis, The University of New South Wales (2010) · Zbl 1249.11071  Caflish R.E., Morokoff W.J., Owen A.B.: Valuation of mortgage backed securities using Brownian Bridges to reduce effective dimension. J. Comput. Finance 1, 27–46 (1997)  Dick, J.: On the fast component-by-component algorithm for polynomial lattice rules. http://quasirandomideas.wordpress.com/2009/12/31/fast-cbc-for-polynomial-lattice-rules , Posted on December 31st 2009, Last accessed February 2nd 2010  Dick, J., Gnewuch, M.: Embedding theorems for fractional spaces and numerical integration (in preparation) · Zbl 1312.65002  Dick J., Kuo F., Pillichshammer F., Sloan I.: Construction algorithms for polynomial lattice rules for multivariate integration. Math. Comput. 74, 1895–1921 (2005) · Zbl 1079.65007 · doi:10.1090/S0025-5718-05-01742-4  Dick J., Pillichshammer F.: Multivariate integration in weighted Hilbert spaces based on Walsh functions and weighted Sobolev spaces. J. Complex. 21, 149–195 (2005) · Zbl 1085.41021 · doi:10.1016/j.jco.2004.07.003  Dick, J., Pillichshammer, F.: Digital nets and sequences, discrepancy and quasi-monte carlo integration. Cambridge University Press, Cambridge (to appear, 2010) · Zbl 1282.65012  Heinrich S., Hickernell F.J., Yue R.X.: Optimal quadrature for haar wavelet spaces. Math. Comput. 73, 259–277 (2004) · Zbl 1035.65004  Hickernell F.J., Woźniakowski H.: The price of pessimism for multidimensional quadrature. J. Complex. 17, 625–659 (2001) · Zbl 1006.65022 · doi:10.1006/jcom.2001.0593  Hickernell F.J., Yue R.X.: The mean square discrepancy of scrambled (t,s)-sequences. SIAM J. Numer. Anal. 38, 1089–1112 (2000) · Zbl 1049.65005 · doi:10.1137/S0036142999358019  Hong H.S., Hickernell F.J.: Algorithm 823: implementing scrambled digital sequences. ACM Trans. Math. Softw. 29, 95–109 (2003) · Zbl 1068.11049 · doi:10.1145/779359.779360  Joe S., Kuo F.Y.: Remark on algorithm 659: implementing Sobol’s quasirandom sequence generator. ACM Trans. Math. Softw. 29, 49–57 (2003) · Zbl 1070.65501 · doi:10.1145/641876.641879  Korobov N.M.: Properties and calculation of optimal coefficients. Dokl. Akad. Nauk SSSR. 132, 1009–1012 (1960) (in Russian) · Zbl 0094.11204  Larcher G., Lauss A., Niederreiter H., Schmid W.Ch.: Optimal polynomials for (t,m,s)-nets and numerical integration of multivariate Walsh series. SIAM J. Numer. Anal. 33, 2239–2253 (1996) · Zbl 0861.65019 · doi:10.1137/S0036142994264705  Larcher G., Traunfellner C.: On the numerical integration of Walsh series by number-theoretic methods. Math. Comput. 63, 277–291 (1994) · Zbl 0806.65013 · doi:10.1090/S0025-5718-1994-1234426-9  Lemieux Ch., L’Ecuyer P.: Randomized polynomial lattice rules for multivariate integration and simulation. SIAM J. Sci. Comput. 24, 1768–1789 (2003) · Zbl 1071.11049 · doi:10.1137/S1064827501393782  Matoušek J.: On the L 2-discrepancy for anchored boxes. J. Complex. 14, 527–556 (1998) · Zbl 0942.65021 · doi:10.1006/jcom.1998.0489  Matoušek J.: Geometric Discrepancy, Algorithms and Combinatorics, vol. 18. Springer, Berlin (1999)  Niederreiter H.: Point sets and sequences with small discrepancy. Monatsh. Math. 104, 273–337 (1987) · Zbl 0626.10045 · doi:10.1007/BF01294651  Niederreiter, H.: Random number generation and quasi-Monte Carlo methods, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (1992) · Zbl 0761.65002  Niederreiter H.: Low-discrepancy point sets obtained by digital constructions over finite fields. Czech. Math. J. 42, 143–166 (1992) · Zbl 0757.11024  Novak E.: Deterministic and stochastic error bounds in numerical analysis. Lecture Notes in Mathematics, vol. 1349. Springer, Berlin (1988) · Zbl 0656.65047  Nuyens D., Cools R.: Fast algorithms for component-by-component constructions of rank-1 lattice rules in shift-invariant reproducing kernel Hilbert spaces. Math. Comput. 75, 903–920 (2006) · Zbl 1094.65004 · doi:10.1090/S0025-5718-06-01785-6  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. 373–388. Springer, Berlin (2006) · Zbl 1099.65006  Owen A.B.: Randomly permuted (t,m,s)-nets and (t,s)-sequences. In: Niederreiter, H., Jau-Shyong Shiue, P. (eds) Monte Carlo and quasi-Monte Carlo Methods in Scientific Computing, pp. 299–317. Springer, New York (1995) · Zbl 0831.65024  Owen A.B.: Monte Carlo variance of scrambled net quadrature. SIAM J. Numer. Anal. 34, 1884–1910 (1997) · Zbl 0890.65023 · doi:10.1137/S0036142994277468  Owen A.B.: Scrambled net variance for integrals of smooth functions. Ann. Stat. 25, 1541–1562 (1997) · Zbl 0886.65018 · doi:10.1214/aos/1031594731  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, Berlin (2002) · Zbl 1112.65304  Sloan I.H., Joe S.: Lattice Methods for Multiple Integration. Oxford Science Publications, The Clarendon Press Oxford University Press, New York (1994) · Zbl 0855.65013  Sloan I.H., Reztsov A.V.: Component-by-component construction of good lattice rules. Math. Comput. 71, 263–273 (2002) · Zbl 0985.65018  Sloan I.H., Woźniakowski H.: When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?. J. Complex. 14, 1–33 (1998) · Zbl 1032.65011 · doi:10.1006/jcom.1997.0463  Yue R.X.: Variance of quadrature over scrambled unions of nets. Stat. Sinica 9, 451–473 (1999) · Zbl 0952.65001  Yue R.X., Hickernell F.J.: The discrepancy and gain coefficients of scrambled digital nets. J. Complex. 18, 135–151 (2002) · Zbl 1114.11306 · doi:10.1006/jcom.2001.0630  Yue R.X., Hickernell F.J.: Strong tractability of integration using scrambled Niederreiter points. Math. Comput. 74, 1871–1893 (2005) · Zbl 1079.65011 · doi:10.1090/S0025-5718-05-01755-2  Yue R.X., Mao S.S.: On the variance of quadrature over scrambled nets and sequences. Stat. Probab. Lett. 44, 267–280 (1999) · Zbl 0970.65006 · doi:10.1016/S0167-7152(99)00018-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.