Component-by-component construction of good QMC rules
by
Frances Kuo
Department of Mathematics, University of Waikato, New Zealand
Coauthors: Stephen Joe (Department of Mathematics, University of Waikato, New Zealand), Ian Sloan (School of Mathematics, University of New South Wales, Australia)

Quasi-Monte Carlo (QMC) rules are equal-weight quadrature rules in which the quadrature points are chosen in a deterministic manner. Theorems have been known for many years that assert the existence of `good' QMC rules. Since none of these existence theorems were constructive, good rules were found in the past by exhaustive searches. The cost of such searches grows exponentially with the dimension d; too expensive for practical purposes.

We present and justify an algorithm for the construction of shifted rank-1 lattice rules for multi-variate integration in weighted Sobolev spaces of non-periodic functions. Our construction is inspired by the recent paper [1]. The parameters characterising the shifted lattice rule are found `component-by-component': the (d+1)-th component of the generator vector and the shift are obtained by successive 1-dimensional searches, with the previous d components kept unchanged. The total cost of a search for rules having n points in all dimensions 1 to d is of order O(n³d²). The present setting is different from that in [1], because the spaces are now weighted Sobolev spaces instead of unweighted Korobov spaces, and there is the extra difficulty of having to find a suitable shift.

A QMC rule is said to be `strongly QMC tractable' if the minimal number of quadrature points needed to reduce the worst-case error from its initial value by a factor \epsilon > 0 is bounded by a polynomial in \epsilon^-1 and independent of d. We show that for n prime, the rules constructed in this way are strongly QMC tractable.

[1] Sloan, I. H. and Reztsov, A. V. (2000). Component-by-component construction of good lattice rules, Math. Comp., to appear.

Date received: October 16, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caek-62.