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)

 

Construction algorithms for polynomial lattice rules for multivariate integration


Authors: J. Dick, F. Y. Kuo, F. Pillichshammer and I. H. Sloan
Journal: Math. Comp. 74 (2005), 1895-1921
MSC (2000): Primary 65C05, 65D30
Published electronically: May 5, 2005
MathSciNet review: 2164102
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We introduce a new construction algorithm for digital nets for integration in certain weighted tensor product Hilbert spaces. The first weighted Hilbert space we consider is based on Walsh functions. Dick and Pillichshammer calculated the worst-case error for integration using digital nets for this space. Here we extend this result to a special construction method for digital nets based on polynomials over finite fields. This result allows us to find polynomials which yield a small worst-case error by computer search. We prove an upper bound on the worst-case error for digital nets obtained by such a search algorithm which shows that the convergence rate is best possible and that strong tractability holds under some condition on the weights.

We extend the results for the weighted Hilbert space based on Walsh functions to weighted Sobolev spaces. In this case we use randomly digitally shifted digital nets. The construction principle is the same as before, only the worst-case error is slightly different. Again digital nets obtained from our search algorithm yield a worst-case error achieving the optimal rate of convergence and as before strong tractability holds under some condition on the weights. These results show that such a construction of digital nets yields the until now best known results of this kind and that our construction methods are comparable to the construction methods known for lattice rules.

We conclude the article with numerical results comparing the expected worst-case error for randomly digitally shifted digital nets with those for randomly shifted lattice rules.


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


Similar Articles

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

Retrieve articles in all journals with MSC (2000): 65C05, 65D30


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: School of Mathematics, The University of New South Wales, Sydney, New South Wales 2052, Australia
Email: fkuo@maths.unsw.edu.au

F. Pillichshammer
Affiliation: Institut für Analysis, Universität Linz, Altenbergstraße 69, A-4040 Linz, Austria
Email: friedrich.pillichshammer@jku.at

I. H. Sloan
Affiliation: School of Mathematics, The University of New South Wales, Sydney, New South Wales 2052, Australia
Email: sloan@maths.unsw.edu.au

DOI: http://dx.doi.org/10.1090/S0025-5718-05-01742-4
PII: S 0025-5718(05)01742-4
Keywords: Quasi--Monte Carlo, numerical integration, polynomial lattice rules
Received by editor(s): January 9, 2004
Received by editor(s) in revised form: May 4, 2004
Published electronically: May 5, 2005
Article copyright: © Copyright 2005 American Mathematical Society