A construction of polynomial lattice rules with small gain coefficients (Q644778): Difference between revisions

The well-distributed nets and sequences in the \(s\)-dimensional unit cube \([0,1)^{s}\) have many applications in different branches of the numerical methods, especially to the theory of quasi-Monte Carlo integration. The so-called digital nets and polynomial lattice rules are important for quasi-Monte Carlo integration. In the present paper the polynomial lattice rules, which have in some sense, small gain coefficients by using component-by-component (CBC) algorithm are constructed. For approximate calculation of the integral \(\int_{[0,1]^{s}} f ({\mathbf x}) d {\mathbf x},\) where the integrand \(f\) belongs to a given functional class, the quasi-Monte Carlo rules \(\hat{I}(f) = {1 \over b^{m}} \sum_{h=0}^{b^{m}-1} f({\mathbf y}_{h}),\) where the points \(\{{\mathbf y}_{h}\}_{h=0}^{b^{m}-1}\) are obtained by applying the scrambling algorithm to a polynomial lattice rules, is used. The variance of the estimator \(\hat{I}(f)\) is investigated. The aim of the paper is to find polynomial lattice rules for which the weighted sum of gain coefficients is minimized. In Section 2, the polynomial lattice rules are reminded. The scrambling algorithm of Owen is described. The definition of Walsh functions is briefly recalled. The space \({\mathcal F}_{\alpha, s, \gamma}\) of functions with finite weighted norm is defined. The generalized variation in the sense of Vitali of order \(0 < \alpha \leq 1\) is defined. In Section 3, the variance of the estimator \(\hat{I}(f) = {1 \over b^{m}} \sum_{h=0}^{b^{m}-1} f({\mathbf y}_{h}),\) where the points \(\{{\mathbf y}_{h}\}_{h=0}^{b^{m}-1}\) are obtained by applying the scrambling algorithm to a digital \((t, m, s)\)-net over \(\mathbb Z_{b},\) is investigated. In Corollary 2, an explicit formula for the worst-case variance of the multivariate integration in the space \({\mathcal F}_{\alpha, s, \gamma}\) using a scrambled quasi-Monte Carlo rule is obtained. In Section 4, it is shown how to construct a polynomial lattice rule using a CBC approach such that the worst-case variance of the multivariate integration in the space \({\mathcal F}_{\alpha, s, \gamma}\) converges at a rate of \(N^{-1 - 2 \alpha + \delta},\) for any \(\delta > 0.\) In Algorithm 1, the CBC algorithm is described. Theorem 1 shows that Algorithm 1 indeed constructs a generated vector such that the above variance has a rate of \(N^{-1 - 2 \alpha + \delta},\) for any \(\delta > 0.\) Corollary 3 shows the tractability of Algorithm 1. In Section 5, Korobov polynomial lattice rules are constructed. This is made in Algorithm 2. In Theorem 2, an upper estimation of the worst-case variance of the integration in the space \({\mathcal F}_{\alpha, s, \gamma}\) by using the lattice rules constructed by using Algorithm 2 is obtained. Corollary 4 discusses the tractability of Algorithm 2. In Section 6, a lower bound of the worst-case variance is obtained. Theorem 3 presents the lower bound of the worst-case variance, which applies the all randomized algorithms. In Section 7, an implementation of the CBC algorithm is realized. In Algorithm 3, a fast version of CBC is described. In Corollary 5 the time \({\mathcal O}(s b^{m}m)\) and the memory \({\mathcal O}(b^{m})\) are obtained. In Section 8, the performance of the CBC algorithm is numerically investigated. The performance of the CBC algorithm is compared with the performance of digital nets.