On the step-by-step construction of quasi--Monte Carlo integration rules that achieve strong tractability error bounds in weighted Sobolev spaces

Abstract

We develop and justify an algorithm for the construction of quasi–Monte Carlo (QMC) rules for integration in weighted Sobolev spaces; the rules so constructed are shifted rank-1 lattice rules. 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 rules constructed in this way are shown to achieve a strong tractability error bound in weighted Sobolev spaces. A search for $n$-point rules with $n$ prime and all dimensions 1 to $d$ requires a total cost of $O(n^3d^2)$ operations. This may be reduced to $O(n^3d)$ operations at the expense of $O(n^2)$ storage. Numerical values of parameters and worst-case errors are given for dimensions up to 40 and $n$ up to a few thousand. The worst-case errors for these rules are found to be much smaller than the theoretical bounds.