We develop a fast algorithm for the construction of good rank-1 lattice rules which are a quasi-Monte Carlo method for the approximation of multivariate integrals. A popular method to construct such rules is the component-by-component algorithm which is able to construct good lattice rules that achieve the optimal theoretical rate of convergence. The construction time of this algorithm is O(s2n2), or O(sn2) when using O(n) memory, for an s-dimensional lattice rule with n points.
We show how to construct good lattice rules in time O(sn log(n)), using O(n) memory, by means of a new algorithm, called the fast component-by-component algorithm. First this is shown for the base case when n is a prime number and the underlying function space is a weighted, shift-invariant and tensor-product reproducing kernel Hilbert space. Then we show that, by a minor increase in construction cost, also more generally weighted function spaces can be handled by the fast algorithm. In particular we show this for order-dependent weights.
When n is not a prime number it turns out that fast construction is also possible, although the construction is more involved for numbers n which have a large number of unique prime factors. An additional advantage is obtained when choosing n to be a prime power, since then the rules are embedded for increasing powers of the prime. Using this embedding, we propose a new fast algorithm to construct lattice sequences which can be used point by point.
Two natural extensions of the algorithm are the construction of polynomial lattice rules and so called copy rules. We show that also here the fast component-by-component algorithm can be applied. The quality of the constructed point sets is finally demonstrated on some finance and statistics examples.
The penultimate version of my PhD thesis text.
And the slides: beamer mode and handout mode.
The code is also available.
Meer en meer wil men hoogdimensionale integralen kunnen uitrekenen. In bijvoorbeeld de financiële wiskunde en de fysica komt men gemakkelijk integralen tegen met honderden of duizenden dimensies. Voor het benaderen van zulke integralen maakt men vaak gebruik van de Monte Carlo methode die hiervoor een gemiddelde neemt van een groot aantal functiewaarden. Deze methode werkt echter nogal traag doordat ze veel functie-evaluaties nodig heeft.
Een alternatief is de quasi-Monte Carlo methode waarbij men de functie in welgekozen punten evalueert. Hierdoor bekomt men veel sneller een goed resultaat met veel minder functie-evaluaties. Het zoeken van zulke goede puntenverzamelingen vergt heel wat rekentijd.
Deze thesis stelt een nieuw algoritme voor om dit zoekproces danig te versnellen. Zo kunnen we met het nieuwe algoritme bijvoorbeeld 100 miljoen punten construeren in 20 dimensies op 10 minuten tijd. Voordien zou dit meer dan 100 jaar gekost hebben. Op basis van dit nieuwe algoritme kunnen we op een snelle manier puntenrijen construeren voor het benaderen van integralen met duizenden dimensies.
