Monthly Archives: December 2009

On the fast component-by-component algorithm for polynomial lattice rules

We present some simplification and observations concerning the fast component-by-component algorithm for polynomial lattice rules. This algorithm was introduced by Nuyens and Cools in

D. Nuyens and R. Cools. Fast component-by-component construction, a reprise for different kernels. In H. Niederreiter and D. Talay, editors, Monte Carlo and Quasi-Monte Carlo Methods 2004, pages 371–385. Springer-Verlag, 2006. Cited on pp. 82, 153, 178. See also Chapter 6 of Dirk’s PhD Thesis.

Let {\boldsymbol{x} = (x_1,\ldots, x_s)} and {x_i = \xi_{i,1} b^{-1} + \xi_{i,2} b^{-2} + \cdots} be the {b} adic expansion of {x} (unique in the sense that infinitely many of the {\xi_{i,j}} are different from {b-1}). We use the notation as in the book. Assume that {b} is a prime number. For the sake of definiteness, consider the mean square worst-case error Continue reading