Quasi-Monte Carlo Methods: Component-by-Component Algorithms

PhD defense

Onyekachi Osisiogu

Two main concepts are commonly used in the literature on quasi-Monte Carlo (QMC) methods when finding integration node sets of high-quality QMC rules with good properties. On the one hand, these are lattice point sets and lattice sequences. The other class of commonly used QMC integration nodes is that of (digital) $(t, m, d)$-nets and $(t,d)$-sequences, where a special instance of $(t,m,d)$-nets, namely so-called polynomial lattice point sets, is also of interest.

In this thesis, we study, in particular, efficient algorithms for constructing rank-1 lattice rules and polynomial lattice rules. In both cases, given the number of points $N$ and the dimension $d$, they are entirely determined by the choice of a generating vector. A well-known algorithm to construct such rules has been established, namely the component-by-component (CBC) algorithm, which can build both good lattice rules and good polynomial lattice rules in multivariate function spaces.

Motivated by earlier work of Korobov from 1963 and 1982, we study variants of CBC search algorithms for good lattice rules and polynomial lattice rules. We show that the resulting rules exhibit a convergence rate in weighted function spaces that can be arbitrarily close to the optimal rate. Moreover, contrary to most other algorithms, we often do not need to know the smoothness of our integrands in advance; the generating vector will still recover the convergence rate associated with the smoothness of the particular integrand and, under appropriate conditions on the weights, the error bounds can be stated without dependence on the dimension $d$. The search algorithms presented are a component-by-component digit-by-digit algorithm and a particular version of the component-by-component algorithm. The algorithms can be implemented in a fast manner reducing the construction cost to $\calO(dN \ln N)$ with $N$ the number of points and $d$ the dimension, and we illustrate our findings with extensive numerical results.