Mathematics of Computation

Author(s): Josef Dick; Friedrich Pillichshammer; Benjamin J. Waterhouse.
Journal: Math. Comp. 77 (2008), 2345-2373.
MSC (2000): Primary 11K45, 65C05, 65D30
Posted: May 1, 2008
Retrieve article in: PDF DVI PostScript

Abstract: It has been shown by Hickernell and Niederreiter that there exist generating vectors for integration lattices which yield small integration errors for $n = p, p^2, \ldots$ for all integers $p \ge 2$ . This paper provides algorithms for the construction of generating vectors which are finitely extensible for $n = p, p^2, \ldots$ for all integers $p \ge 2$ . The proofs which show that our algorithms yield good extensible rank-1 lattices are based on a sieve principle. Particularly fast algorithms are obtained by using the fast component-by-component construction of Nuyens and Cools. Analogous results are presented for generating vectors with small weighted star discrepancy.

1.: N. Aronszajn, Theory of reproducing kernels. Trans. Amer. Math. Soc., 68 (1950), 337-404. MR 0051437 (14:479c)
2.: R. Cools, F.Y. Kuo and D. Nuyens, Constructing embedded lattice rules for multivariate integration. SIAM J. Sci., 28 (2006), 2162-2188. Comput. MR 2272256 (2007m:68324)
3.: J. Dick, On the convergence rate of the component-by-component construction of good lattice rules. J. Complexity, 20 (2004), 493-522. MR 2068155 (2005h:65035)
4.: J. Dick, The construction of extensible polynomial lattice rules with small weighted star discrepancy. Math. Comp., 76 (2007), 2077-2085. MR 2336283
5.: J. Dick, I.H. Sloan, X. Wang and H. Woźniakowski, Liberating the weights. J. Complexity, 20 (2004), 593-623. MR 2086942 (2005h:65008)
6.: J. Dick, I.H. Sloan, X. Wang and H. Woźniakowski, Good lattice rules in weighted Korobov spaces with general weights. Numerische Mathematik, 103 (2006), 63-97. MR 2207615 (2006m:65014)
7.: J. Dick and X. Wang, A hybrid construction method for good lattice rules in weighted Korobov spaces. Preprint.
8.: G.H. Hardy and E.M. Wright, An Introduction to the Theory of Numbers, 5th Ed., Clarendon Press, Oxford, 1979. MR 568909 (81i:10002)
9.: F.J. Hickernell, A generalized discrepancy and quadrature error bound. Math. Comp., 67 (1998), 299-322. MR 1433265 (98c:65032)
10.: F.J. Hickernell, My dream quadrature rule. J. Complexity, 19 (2003), 420-427. MR 1984124 (2004e:41034)
11.: F.J. Hickernell and H.S. Hong, Computing multivariate normal probabilities using rank- lattice sequences. Scientific computing (Hong Kong, 1997), pp. 209-215, Springer, Singapore, 1997. MR 1729661
12.: F.J. Hickernell, H.S. Hong, P. L'Ecuyer and C. Lemieux, Extensible lattice sequences for quasi-Monte Carlo quadrature. SIAM J. Sci. Comput., 22 (2000), 1117-1138. MR 1785348 (2001h:65032)
13.: F.J. Hickernell and H. Niederreiter, The existence of good extensible rank-1 lattices. J. Complexity, 19 (2003), 286-300. MR 1984115 (2004c:65015)
14.: F.J. Hickernell and H. Woźniakowski, Tractability of multivariate integration for periodic functions. J. Complexity, 17 (2001), 660-682. MR 1881663 (2003g:65028)
15.: S. Joe, Construction of good rank-1 lattice rules based on the weighted star discrepancy. In: Monte Carlo and Quasi-Monte Carlo Methods 2004. (Niederreiter H. and Talay D., eds.), pp. 181-196, Springer, Berlin, Heidelberg, New York, 2006. MR 2208709 (2006m:65048)
16.: F.Y. Kuo, Component-by-component constructions achieve the optimal rate of convergence for multivariate integration in weighted Korobov and Sobolev spaces. J. Complexity, 19 (2003), 301-320. MR 1984116 (2004c:41066)
17.: F.Y. Kuo and S. Joe, Component-by-component construction of good lattice rules with composite number of points. J. Complexity, 18 (2002), 943-976. MR 1933697 (2003j:65016)
18.: G. Larcher, On the distribution of an analog to classical Kronecker-sequences. J. Number Theory, 52 (1995), 198-215. MR 1336745 (96g:11098)
19.: G. Larcher and H. Niederreiter, Generalized -sequences, Kronecker-type sequences, and Diophantine approximations of formal Laurent series. Trans. Amer. Math. Soc., 347 (1995), 2051-2073. MR 1290724 (95i:11086)
20.: H. Niederreiter, Quasi-Monte Carlo methods and pseudo-random numbers. Bull. Amer. Math. Soc., 84 (1978), 957-1041. MR 508447 (80d:65016)
21.: H. Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods, CBMS-NSF Series in Applied Mathematics 63, SIAM, Philadelphia, 1992. MR 1172997 (93h:65008)
22.: H. Niederreiter, The existence of good extensible polynomial lattice rules. Monatsh. Math., 139 (2003), 295-307. MR 2001711 (2004j:11087)
23.: H. Niederreiter, Constructions of -nets and -sequences. Finite Fields and their Applications, 11 (2005), 578-600. MR 2158777 (2006c:11090)
24.: D. Nuyens and R. Cools, 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. MR 2196999 (2007a:65032)
25.: D. Nuyens and R. Cools, Fast construction of rank-1 lattice rules with a non-prime number of points. J. Complexity, 22 (2006), 4-28. MR 2198499 (2006k:65063)
26.: I.F. Sharygin, A lower estimate for the error of quadrature formulas for certain classes of functions. Zh. Vychisl. Mat. i Mat. Fiz., 3 (1963), 370-376. MR 0150952 (27:938)
27.: V. Sinescu and S. Joe, 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 (A. Keller, S. Heinrich and H. Niederreiter, eds.), Springer-Verlag, Berlin, Heidelberg, pp. 645-658.
28.: I.H. Sloan, S. Joe, Lattice Methods for Multiple Integration, Oxford University Press, Oxford, 1994. MR 1442955 (98a:65026)
29.: I.H. Sloan, F.Y. Kuo and S. Joe, Constructing randomly shifted lattice rules in weighted Sobolev spaces. SIAM J. Numer. Anal., 40 (2002), 1650-1665. MR 1950616 (2003m:65031)
30.: I.H. Sloan and H. Woźniakowski, When are quasi-Monte Carlo algorithms efficient for high-dimensional integrals? J. Complexity, 14 (1998), 1-33. MR 1617765 (99d:65384)
31.: X. Wang, I.H. Sloan and J. Dick, On Korobov lattice rules in weighted spaces. SIAM J. Numer. Anal., 42 (2004), 1760-1779. MR 2114300 (2005j:65006)

Retrieve articles in Mathematics of Computation with MSC (2000): 11K45, 65C05, 65D30

Josef Dick
Affiliation: School of Mathematics and Statistics, University of New South Wales, Sydney 2052, Australia
Email: josi@maths.unsw.edu.au

Friedrich Pillichshammer
Affiliation: Institut für Finanzmathematik, Universität Linz, Altenbergstrasse 69, A-4040 Linz, Austria
Email: friedrich.pillichshammer@jku.at

Benjamin J. Waterhouse
Affiliation: School of Mathematics and Statistics, University of New South Wales, Sydney 2052, Australia
Email: benjw@maths.unsw.edu.au

DOI: 10.1090/S0025-5718-08-02009-7
PII: S 0025-5718(08)02009-7
Keywords: Quasi-Monte Carlo, numerical integration, extensible lattice rule, component-by-component construction
Received by editor(s): June 13, 2006
Received by editor(s) in revised form: December 8, 2006
Posted: May 1, 2008
Additional Notes: This work was supported by the Austrian Research Foundation (FWF), Project S 9609, that is part of the Austrian Research Network ``Analytic Combinatorics and Probabilistic Number Theory''.
The support of the Australian Research Council under its Centre of Excellence program is gratefully acknowledged.
Copyright of article: Copyright 2008, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS