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)

 

Fast algorithms for component-by-component construction of rank-$ 1$ lattice rules in shift-invariant reproducing kernel Hilbert spaces


Authors: Dirk Nuyens and Ronald Cools
Journal: Math. Comp. 75 (2006), 903-920
MSC (2000): Primary 65D30, 65D32, 68W40
Published electronically: January 4, 2006
MathSciNet review: 2196999
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We reformulate the original component-by-component algorithm for rank-$ 1$ lattices in a matrix-vector notation so as to highlight its structural properties. For function spaces similar to a weighted Korobov space, we derive a technique which has construction cost $ O(s n \log(n))$, in contrast with the original algorithm which has construction cost $ O(s n^2)$. Herein $ s$ is the number of dimensions and $ n$ the number of points (taken prime). In contrast to other approaches to speed up construction, our fast algorithm computes exactly the same quantity as the original algorithm. The presented algorithm can also be used to construct randomly shifted lattice rules in weighted Sobolev spaces.


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


Similar Articles

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

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


Additional Information

Dirk Nuyens
Affiliation: Katholieke Universiteit Leuven, Department of Computer Science, Celestijnenlaan 200A, B-3001 Heverlee, Belgium
Email: dirk.nuyens@cs.kuleuven.be

Ronald Cools
Affiliation: Katholieke Universiteit Leuven, Department of Computer Science, Celestijnenlaan 200A, B-3001 Heverlee, Belgium
Email: ronald.cools@cs.kuleuven.be

DOI: http://dx.doi.org/10.1090/S0025-5718-06-01785-6
PII: S 0025-5718(06)01785-6
Keywords: Numerical integration, quasi--Monte Carlo, rank-$1$ lattice rules, component-by-component construction, fast algorithms
Received by editor(s): June 22, 2004
Received by editor(s) in revised form: November 26, 2004
Published electronically: January 4, 2006
Additional Notes: This research is part of a project financially supported by the Onderzoeksfonds K.U.Leuven / Research Fund K.U.Leuven
Article copyright: © Copyright 2006 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.