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

An algorithm for the construction of quasi-Monte Carlo rules for integration in weighted Sobolev spaces is developed and justified; 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 srong 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.