Efficient calculation of the worst-case error and (fast) component-by-component construction of higher order polynomial lattice rules (Q664602)

An important problem in the theory of quasi-Monte Carlo integration is the consideration of functional spaces, and the construction of well distributed \(s\)-dimensional nets, which are to be the nodes of the integration, and to provide an optimal order of the worst-case error. In the present paper the authors introduce the functional space \({\mathcal W}_{\alpha, s, \gamma},\) which forms a Korobov space. This functional space contains functions with certain decay rate of their Fourier-Walsh coefficients. The concept of the so-called higher order polynomial lattice point sets is given, and these sets are used in the practice of quasi-Monte Carlo integration in the space \({\mathcal W}_{\alpha, s, \gamma}.\) In the introduction of the article, the main ideas of quasi-Monte Carlo rules are reminded. Some constructive principles of \(b\)-adic digital nets are discussed. The order of the worst-case error of the integration in some functional classes is considered. In Section 2 some preliminary natations, related with using Walsh functions in base \(b,\) are presented. The concept of the functional space \({\mathcal W}_{\alpha, s, \gamma}\) is developed. In Definition 1 the construction scheme of digital nets is given. In Definition 2 the concept of the dual digital nets is presented. In Definitions 3 and 4 the details of the polynomial lattice rules and their dual polynomial lattice are presented. In Algorithm 1 the component-by-component (CBC) construction of higher order polynomial lattice rules is developed. In Theorem 1 an estimation of the worst-case error of the integration is obtained. It is shown that the sets constructed in Algorithm 1 achieve almost optimal rates of convergence of the worst-case error of the integration in the space \({\mathcal W}_{\alpha, s, \gamma}.\) In Lemma 1 an explicit formula for the worst-case error of the integration in the space \({\mathcal W}_{\alpha, s, \gamma}\) is obtained. In Section 3 it is shown how to efficiently calculate the worst-case error obtained in Lemma 1, and how the construction of higher order polynomial lattice rules can be done using the fast CBC approach. The worst-case error is analysed. In Algorithm 2 the fast CBC construction of higher order polynomial lattice rules is given. In Section 4 it is shown how to calculate the infinite sum \(\omega_{\alpha}(x)\) from the formula for the worst-case error. First an explicit formula for the quantity \(\omega_{\alpha}(x)\) is obtained. In Theorem 2 it is shown that, if \(x\) can be represented with \(n\) digits in base \(b,\) then \(\omega_{\alpha}(x)\) can be computed through \({\mathcal O}(\alpha n)\) operations. In Theorem 3 explicit forms of \(\omega_{\alpha}(x)\) for general \(x \in [0,1)\) and small \(\alpha\) are given. Corollary 1 considers the main results of Theorem 3 in the case when \(b=2.\) In Section 5 the explicit constructions, based on using the CBC algorithm and the fast CBC construction of higher order polynomial lattice rules, are compared. The numerical data in the tests show that the new construction produces better results.