Reducing the construction cost of the componentbycomponent construction of good lattice rules
Authors:
J. Dick and F. Y. Kuo
Journal:
Math. Comp. 73 (2004), 19671988
MSC (2000):
Primary 65D30, 65D32; Secondary 68Q25
Published electronically:
August 19, 2003
MathSciNet review:
2059746
Fulltext 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 componentbycomponent 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 componentbycomponent is only operations. This reduction in cost allows, in practice, construction of rules with millions of points. The rules constructed again achieve a worstcase 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
(14,479c), http://dx.doi.org/10.1090/S00029947195000514377
 2.
Dick, J. (2003). On the convergence rate of the componentbycomponent 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). QuasiMonte 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, 5977.
 5.
Loo
Keng Hua and Yuan
Wang, Applications of number theory to numerical analysis,
SpringerVerlag, Berlin, 1981. Translated from the Chinese. MR 617192
(83g:10034)
 6.
N.
M. Korobov, Properties and calculation of optimal
coefficients, Soviet Math. Dokl. 1 (1960),
696–700. MR 0120768
(22 #11517)
 7.
Kuo, F. Y. (2003). Componentbycomponent constructions achieve the optimal rate of convergence for multivariate integration in weighted Korobov and Sobolev spaces, J. Complexity, 19, 301320.
 8.
Kuo, F. Y. and Joe, S. (2002). Componentbycomponent construction of good lattice rules with a composite number of points, J. Complexity, 18, 943976.
 9.
Sloan, I. H., Kuo, F. Y. and Joe, S. (2002). On the stepbystep construction of quasiMonte Carlo integration rules that achieve strong tractability error bounds in weighted Sobolev spaces, Math. Comp., 71, 16091640.
 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, 16501665.
 11.
I.
H. Sloan and A.
V. Reztsov, Componentbycomponent construction of
good lattice rules, Math. Comp.
71 (2002), no. 237, 263–273. MR 1862999
(2002h:65028), http://dx.doi.org/10.1090/S0025571801013424
 12.
Ian
H. Sloan and Henryk
Woźniakowski, When are quasiMonte Carlo algorithms
efficient for highdimensional integrals?, J. Complexity
14 (1998), no. 1, 1–33. MR 1617765
(99d:65384), http://dx.doi.org/10.1006/jcom.1997.0463
 13.
Sloan, I. H. and Wozniakowski, H. (2001). Tractability of multivariate integration for weighted Korobov classes, J. Complexity, 17, 697721.
 1.
 Aronszajn, N. (1950). Theory of reproducing kernels, Trans. Amer. Math. Soc., 68, 337404. MR 14:479c
 2.
 Dick, J. (2003). On the convergence rate of the componentbycomponent 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). QuasiMonte 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, 5977.
 5.
 Hua, L. K. and Wang, Y. (1981). Applications of number theory to numerical analysis, Springer Verlag, Berlin; Science Press, Beijing. MR 83g:10034
 6.
 Korobov, N. M. (1960). Properties and calculation of optimal coefficients, Doklady Akademii Nauk SSSR, 132, 100910 (Russian). English transl.: Soviet Mathematics Doklady, 1, 696700. MR 22:11517
 7.
 Kuo, F. Y. (2003). Componentbycomponent constructions achieve the optimal rate of convergence for multivariate integration in weighted Korobov and Sobolev spaces, J. Complexity, 19, 301320.
 8.
 Kuo, F. Y. and Joe, S. (2002). Componentbycomponent construction of good lattice rules with a composite number of points, J. Complexity, 18, 943976.
 9.
 Sloan, I. H., Kuo, F. Y. and Joe, S. (2002). On the stepbystep construction of quasiMonte Carlo integration rules that achieve strong tractability error bounds in weighted Sobolev spaces, Math. Comp., 71, 16091640.
 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, 16501665.
 11.
 Sloan, I. H., Retzsov, A. V. (2002). Componentbycomponent construction of good lattice points, Math. Comp., 71, 263273. MR 2002h:65028
 12.
 Sloan, I. H. and Wozniakowski, H. (1998). When are quasiMonte Carlo algorithms efficient for high dimensional integrals?, J. Complexity, 14, 133. MR 99d:65384
 13.
 Sloan, I. H. and Wozniakowski, H. (2001). Tractability of multivariate integration for weighted Korobov classes, J. Complexity, 17, 697721.
Similar Articles
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:
http://dx.doi.org/10.1090/S0025571803016107
PII:
S 00255718(03)016107
Keywords:
QuasiMonte 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
