Construction algorithms for digital nets with low weighted star discrepancy

摘要

We introduce a new construction method for digital nets which yield point sets in the s-dimensional unit cube with low star discrepancy. The digital nets are constructed using polynomials over finite fields. It has long been known that there exist polynomials which yield point sets with low (unweighted) star discrepancy. This result was obtained by Niederreiter by the means of averaging over all polynomials. Hence concrete examples of good polynomials were not known in many cases. Here we show that good polynomials can be found by computer search. The search algorithm introduced in this paper is based on minimizing a quantity closely related to the star discrepancy.It has been pointed out that many integration problems can be modeled by weighted function spaces and it has been shown that in this case point sets with low weighted discrepancy are required. Hence it is particularly useful to be able to adjust a point set to some given weights. We are able to extend our results from the unweighted case to show that this can be done using our construction algorithms. This way we can find point sets with low weighted star discrepancy, making such point sets especially useful for many applications.