Higher algebra methods for quasi-random point sets

Quasi-random or quasi-Monte Carlo (QMC) point sets are algorithmically produced point sets that are subject to well-specified uniformity criteria; they are mainly applied in highly multi-variate numerical integration, optimization and simulation, with uses in various not directly mathematical areas, most notably in finance. A great leap forward in the construction of high quality point sets has been made by Niederreiter and Xing with their introduction of methods of higher algebra, specifically, algebraic function fields, into the research area of uniform distribution. They could show that with those methods the bounds of the quality parameter are the best that are currently known. However, apart from the work of the applicant there have been no attempts at a computer implementation of these constructions. It is one aim of this project to expand the range of sequences available as generator matrices and computer code for both research and application purposes. To achieve this, not only tools such as libraries for computations in function fields need to be developed but to provide the necessary data also theoretical investigations need to be carried out. Another kind of QMC point sets are lattice rules. They precede (t,s)-sequences (of which the above-mentioned Niederreiter-Xing sequences are a special case) with the work of Hlawka and Korobov. They have been generalized further to polynomial lattice rules, also extensible and higher rank versions of both. This development initially occurred somewhat parallel to the digital paradigm of nets, but in the meantime there has been some convergence. The line of research in a second part of the project will be to apply an abstract viewpoint in order to investigate further generalizations that are possible for the lattice rule approach, e.g., various versions using algebraic function fields and eventually more abstract structures.

Quasi-Monte Carlo methods provide useful tools for various scientific areas, especially when efficient evaluations of highly multivariate numerical integrals are involved. Among these methods, digital sequences are held in particularly high regard due to their quality. In the last two decades, a series of papers presenting constructions of digital sequences using advanced higher algebra methods have appeared, which gave asymptotically optimal error bounds. However, due to the complexity of the methods, they have hitherto seen little use in practice. - The projects goal was to leverage these results for nonspecialist users, as well as provide useful data for researchers.This was achieved in several steps: firstly, making important intermediate results from the papers explicit and integrating them in a pre-existing public database (http://manypoints.org). Secondly, implementing the digital sequence constructions using these data in a (partly publicly accessible) computer algebra system (Magma). Thirdly, producing generator matrices of digital sequences. These generator matrices are the parameters that practitioners can give to pre-existing, third-party software for use in their applications, i.e., at this point no advanced knowledge is needed. Lastly, all implementations and generator matrices, along with additional information have been provided publicly accessible on a dedicated website, http://sites.google.com/sites/isabelpirsic/P23285.