Reducing the construction cost of the component-by-component construction of good lattice rules

Authors:
J. Dick and F. Y. Kuo

Journal:
Math. Comp. **73** (2004), 1967-1988

MSC (2000):
Primary 65D30, 65D32; Secondary 68Q25

Published electronically:
August 19, 2003

MathSciNet review:
2059746

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The construction of randomly shifted rank- lattice rules, where the number of points is a prime number, has recently been developed by Sloan, Kuo and Joe for integration of functions in weighted Sobolev spaces and was extended by Kuo and Joe and by Dick to composite numbers. To construct -dimensional rules, the shifts were generated randomly and the generating vectors were constructed component-by-component at a cost of operations. Here we consider the situation where is the product of two distinct prime numbers and . We still generate the shifts randomly but we modify the algorithm so that the cost of constructing the, now two, generating vectors component-by-component is only operations. This reduction in cost allows, in practice, construction of rules with millions of points. The rules constructed again achieve a worst-case strong tractability error bound, with a rate of convergence for .

**1.**N. Aronszajn,*Theory of reproducing kernels*, Trans. Amer. Math. Soc.**68**(1950), 337–404. MR**0051437**, 10.1090/S0002-9947-1950-0051437-7**2.**Dick, J. (2003).*On the convergence rate of the component-by-component construction of good lattice rules*, J. Complexity, submitted.**3.**Hardy, G. H., Littlewood, J. E. and Pólya, G. (1934).*Inequalities*, Cambridge University Press, Cambridge.**4.**Hickernell, F. J. and Hong, H. S. (2002).*Quasi-Monte Carlo methods and their randomizations*, Applied Probability (R. Chan, Y.-K. Kwok, D. Yao, and Q Zhang, eds.), AMS/IP Studies in Advanced Mathematics 26, American Mathematical Society, Providence, 59-77.**5.**Loo Keng Hua and Yuan Wang,*Applications of number theory to numerical analysis*, Springer-Verlag, Berlin-New York; Kexue Chubanshe (Science Press), Beijing, 1981. Translated from the Chinese. MR**617192****6.**N. M. Korobov,*Properties and calculation of optimal coefficients*, Soviet Math. Dokl.**1**(1960), 696–700. MR**0120768****7.**Kuo, F. Y. (2003).*Component-by-component constructions achieve the optimal rate of convergence for multivariate integration in weighted Korobov and Sobolev spaces*, J. Complexity,**19**, 301-320.**8.**Kuo, F. Y. and Joe, S. (2002).*Component-by-component construction of good lattice rules with a composite number of points*, J. Complexity,**18**, 943-976.**9.**Sloan, I. H., Kuo, F. Y. and Joe, S. (2002).*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**, 1609-1640.**10.**Sloan, I. H., Kuo, F. Y. and Joe, S. (2002).*Constructing randomly shifted lattice rules in weighted Sobolev spaces*, SIAM J. Numer. Anal.,**40**, 1650-1665.**11.**I. H. Sloan and A. V. Reztsov,*Component-by-component construction of good lattice rules*, Math. Comp.**71**(2002), no. 237, 263–273. MR**1862999**, 10.1090/S0025-5718-01-01342-4**12.**Ian H. Sloan and Henryk Woźniakowski,*When are quasi-Monte Carlo algorithms efficient for high-dimensional integrals?*, J. Complexity**14**(1998), no. 1, 1–33. MR**1617765**, 10.1006/jcom.1997.0463**13.**Sloan, I. H. and Wozniakowski, H. (2001).*Tractability of multivariate integration for weighted Korobov classes*, J. Complexity,**17**, 697-721.

Retrieve articles in *Mathematics of Computation*
with MSC (2000):
65D30,
65D32,
68Q25

Retrieve articles in all journals with MSC (2000): 65D30, 65D32, 68Q25

Additional Information

**J. Dick**

Affiliation:
School of Mathematics, The University of New South Wales, Sydney, New South Wales 2052, Australia

Email:
josi@maths.unsw.edu.au

**F. Y. Kuo**

Affiliation:
Department of Mathematics, The University of Waikato, Private Bag 3105, Hamilton, New Zealand

Address at time of publication:
School of Mathematics, The University of New South Wales, Sydney, New South Wales 2052, Australia

Email:
fkuo@maths.unsw.edu.au

DOI:
https://doi.org/10.1090/S0025-5718-03-01610-7

Keywords:
Quasi--Monte Carlo,
numerical integration,
lattice rules

Received by editor(s):
August 23, 2002

Received by editor(s) in revised form:
February 16, 2003

Published electronically:
August 19, 2003

Article copyright:
© Copyright 2003
American Mathematical Society