We study multivariate numerical integration of smooth functions in weighted Sobolev spaces with dominating mixed smoothness
α≥2 defined over the
s-dimensional unit cube. We propose a new quasi-Monte Carlo (QMC)-based quadrature rule, named the extrapolated polynomial lattice rule, which achieves the almost optimal rate of convergence. Extrapolated polynomial lattice rules are constructed in two steps: (i) construction of classical polynomial lattice rules over
Fb with
α consecutive sizes of nodes,
bm−α+1,…,bm, and (ii) recursive application of Richardson extrapolation to a chain of
α approximate values of the integral obtained by consecutive polynomial lattice rules. We prove the existence of good extrapolated polynomial lattice rules achieving the almost optimal order of convergence of the worst-case error in Sobolev spaces with general weights. Then, by restricting to product weights, we show that such good extrapolated polynomial lattice rules can be constructed by the fast component-by-component algorithm under a computable quality criterion. The required total construction cost is of order
(s+α)NlogN, which improves the currently known result for the interlaced polynomial lattice rule, which is of order
sαNlogN. We also study the dependence of the worst-case error bound on the dimension. A big advantage of our method compared to interlaced polynomial lattice rules is that the fast QMC matrix vector method can be used in this setting, while still achieving the same rate of convergence. Such a method was previously not known. Numerical experiments for test integrands support our theoretical result.
In the 1990's copy rules have been studied as an easy and convenient way to construct lattice rules with a huge amount of points. Starting with the analysis of higher-rank lattice rules it was demonstrated numerically by Sloan and Walsh (1990) that copying scaled down rules by
21 or
31th to fill up the unit cube---conveniently only in the f irst few dimensions to avoid a curse of dimensionality by construction---could deliver rules which have a better worst -case error for the standard Korobov space than basic rank-
1 rules. Further results were obtained by Disney and Sloan (1992), Joe and Sloan (1992) and Joe and Disney (1993). More recently, these results were extended to the product weighted Korobov space by Kuo and Joe (2003) in which condit ions on the weights were found to obtain a smaller worst-case error for an (intermediate) copy rule than for a rank-$1 $ rule. (Another recent track, called augmentation sequences, is investigated by Robinson, Li and Hill, but these are not directly relevant to this talk.) Here we present results on polynomial copy rules in a weighted Walsh space. We show some similarities with normal copy rules, as can be expected by the similarities between polynomial lattice rules and normal lattice rules, and some differences which show up in the theory. We derive an expression for the mean of the worst-case error and an existence theorem for polynomial copy rules which will do better than the mean follows from this. Comparing this mean to the mean of normal polynomial lattice rules, we can analyse when copying is expected to be favorable. We remark that, as is the case for normal copy rules, polynomial copy rules can also be constructed by the fast component-by-component construction algorithm.