Fast component-by-component construction, a reprise for different kernels. (English)
Niederreiter, Harald (ed.) et al., Monte Carlo and quasi-Monte Carlo methods 2004. Refereed proceedings of the sixth international conference on Monte Carlo and quasi-Monte Carlo methods in scientific computation, Juan-les-Pins, France, June 7‒10, 2004. Berlin: Springer (ISBN 3-540-25541-9/pbk). 373-387 (2006).
Summary: The authors [Math. Comput. 75, No. 254, 903‒920 (2006; Zbl 1094.65004)] have 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 discuss component-by-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 MC$^2$QMC 2004 by {\it S. Joe} [this volume, 181‒196 (2006; Zbl 1097.65005)] and {\it J. Dick, G. Leobacher} and {\it F. Pillichshammer} [SIAM J. Numer. Anal. 43, No. 1, 76‒95 (2005; Zbl 1084.11040)]. We also give an example implementation of the algorithm in Matlab.