Lattice sequences: from fast construction to rapid application
Dirk Nuyens, Ronald Cools · Lirias · 2007
For high dimensional numerical integration, lattice rules have long been seen as point sets with a predetermined number of points which had to be used all at once. This is highly impractical when one does not know in advance how many points are needed. Recently a lot of work has been done to overcome this problem and theoretical results have shown that it is possible to construct a lattice rule which is extensible in the number of points as well as in the number of dimensions. In a recent paper with Ronald Cools and Frances Y. Kuo a fast construction algorithm was presented which can construct a lattice sequence in time O(s n (log(n))^2), where n is the number of points and s is the number of dimensions (n is a prime power). Such a lattice sequence can be used point by point and guarantees near optimal point distributions for intermediate powers of the prime base. The point set can actually be looked at as a collection of smaller lattice rules, starting at and spanning powers of the base, similar to a (t, m, s)-net. In another recent paper by Josef Dick, Friedrich Pillichshammer and Ben Waterhouse an alternative construction method is presented and more theoretical results are obtained. This talk will present an overview on the fast construction of lattice rules in different shift-invariant weighted spaces, leading to the construction of lattice sequences. Because of the fast construction it has become possible to construct a rule for any suitable weighted space that one might need, without having to rely on stored tables. We will therefore not only argue that, because of the sequence usage, lattice rules are now on par with, e.g., Sobol' points, but that they are indeed a sophisticated tool for the approximation of high dimensional integrals which can even be fine tuned to the problem area itself. On the practical side there are also a lot of points in favor of lattice rules. E.g., the long forgotten trick of periodisation can be used to speed up convergence from O(n^{-1}) to O(n^{-a}), a > 1, if the number of dimensions is only moderately high. This will be shown for the approximation of the multivariate normal distribution in 5 dimensions, which can then be directly used for the pricing of, e.g., lookback options and outperformance options. An extra benefit of lattice sequences is that they are easy to program and generation of the points is almost as fast as generating just pseudo random numbers.