Fast construction of Quasi Monte Carlo points

Within their program “Femtech Praktikum”, the Austrian Research Promotion Agency offers cofunding of internships at research companies to female students of natural or technical sciences.

From November 2019 to April 2020, Judith Barth from Kepler University was such an intern at MathConsult, researching on constructing generating vectors of rank-1 lattice rules for numerical integration, this is what she found out:

The goal of my thesis is to explain, discuss and compare different effective methods for high-dimensional numerical integration of one-periodic functions, which are continuous, smooth and expressible in terms of abso-
lutely convergent Fourier series. For this problem, among other methods, lattice rules have been invented. Lattice rules are equal-weight cubature rules belonging to quasi-Monte Carlo methods, and can be considered as a generalization of the well-known rectangle rule. A rank-1 lattice rule to approximate a d-dimensional integral is fully specied by its generating vector

and its number of cubature points n. This work provides an overview of lattice rules applied to dierent function spaces, especially weighted Korobov spaces as well as different approaches for constructing lattice points, called (reduced fast) component-by-component (CBC) construction and (reduced fast) successive coordinatesearch (SCS) construction.

In CBC algorithms, the parameters defining the lattice rules are obtained by a successive search in each dimension, while keeping the previous components fixed. Due to the small eort of these algorithms, they are very useful for implementations and can be applied in various fields in practice. On the contrary SCS algorithms start with a given initial vector

with the aim of improving its quality and getting closer to the optimal choice of the worst case error. The single components of the starting vector are modified and improved on a step-by-step basis.

The last part of my thesis compares lattice points generated by the introduced CBC/SCS construction methods and the well known Sobol points. My master thesis was supervised by Peter Kritzer, RICAM Linz and supported by Andreas Binder, MathConsult Gmbh, Linz.