Fast Component-by-Component Construction, a Reprise for Different Kernels

Summary In [16] (Nuyens and Cools) it was shown that it is possible to generate rank-1 lattice rules with n points, n being prime, in a fast way. The construction cost in shift-invariant tensor-product reproducing kernel Hilbert spaces was reduced from O(sn 2) to O(sn log(n)), with s the number of dimensions. This reduction in construction cost was made possible by exploiting the algebraic structure of multiplication modulo a prime. Here we look at the applications of the fast algorithm from a practical point of view. Although the choices for the function space are arbitrary, in practice only few kernels are used for the construction of rank-1 lattices. We will discuss componentby-component construction for the worst-case Korobov space, the average-case Sobolev space, the weighted lattice criterion R n,γ and polynomial lattice rules based on the digital Walsh kernel, of which the last two were presented at MC2QMC 2004 by Joe [11] and Dick, Leobacher and Pillichshammer, see e.g. [7]. We also give an example implementation of the algorithm in Matlab.