Construction of interlaced polynomial lattice rules for infinitely differentiable functions (Q2408931)

The quasi-Monte Carlo (CMC) method is an excellent tool for numerical integration. The error of this method depends on the integrand and the nodes of the integration. Usually, the integrands are from some functional class. The nets of the nodes must be carefully designed, depending on the class to which the integrand belongs. In the present paper the multivariate integration over the \(s\)-dimensional unit cube in a weighted space of infinitely differentiable functions is studied. A constructive approach to finding a good QMC rule which achieves a dimensional-independent super-polynomial convergence of the worst-case error is provided. It is proved that interlaced polynomial lattice rules with an interlacing factor can be constructed using a fast component-by-component algorithm in at most \({\mathcal O}(s N (\log N)^2)\) arithmetic operations to achieve a dimension-independent super-polynomial convergence. In the introduction of the paper the QMC method for approximate solving of multivariate integrals are discussed. Also, some techniques for the construction of good polynomial lattice rules are reminded. In Section 2 some necessary background and notations are introduced. The concept of the Walsh functions is reminded. The definition of the weighted function space \({\mathcal F}_{s, {\mathbf u}}\) is given. The concept of the worst-case error of the integration in the space \({\mathcal F}_{s, {\mathbf u}}\) by using a QMC rule is presented. The constructive principles of the polynomial lattice rules and the generating vector are given. In Algorithm 1 the component-by-component construction to find good generating vectors is developed. In Theorem 2 an upper bound of the worst-case error of the integration in the space \({\mathcal F}_{s, {\mathbf u}}\) by using the nodes, constructed in Algorithm 1, in the term of a concave and unbounded monotonic increasing function, is obtained. In Section 3 the worst-case error in the space \({\mathcal F}_{s, {\mathbf u}}\) for QMC rules using a digital net is studied. A computational upper bound of the error is derived. In Section 4 it is proved that the component-by-component algorithm can be used to obtain good interlaced polynomial lattice rules which achieve a dimension-independent super-polynomial convergence of the worst-case error. It is shown how the fast component-by-component construction using the fast Fourier transform can be applied. It is proved that the interlaced polynomial lattice rules achieve dimension-independent super-polynomial convergence of the error. In Section 5 some numerical experiments are presented.