Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

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-$1$ lattice rules, where the number of points $n$ 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 $d$-dimensional rules, the shifts were generated randomly and the generating vectors were constructed component-by-component at a cost of $O(n^2d^2)$ operations. Here we consider the situation where $n$ is the product of two distinct prime numbers $p$ and $q$. 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 $O(n(p+q)d^2)$ 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 $O(p^{-1+\delta}q^{-1/2})$ for $\delta>0$.


References [Enhancements On Off] (What's this?)


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/S0025-5718-03-01610-7
PII: S 0025-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