Fast component-by-component construction of rank-1 lattice rules with a non-prime number of points (Q2489147)

The obtained results of the paper solve the problem of minimizing the worst-case error of quasi-Monte Carlo integration of the functions in the unit ball of a tensor product reproducing kernel weighted Hilbert space. For an approximation of integrals over the \(s\)-dimensional unit cube it is proposed to use an equal weight cubature rule with a rank-1 lattice point sets. The construction of these rank-1 lattice point sets depends on integer vector, called the generating vector of the lattice. The worst-case error of the integration in this functional space over the proposed rank-1 lattice point sets is written in the terms of the generating vector. The main aim is to choose the generating vector which minimizes the worst-case error of the integration. A special algorithm to find the values of the components of the generating vector is proposed, the so-called component-by-component algorithm. The component-by-component algorithm finds values of the components of the generating vector one component at a time, while keeping the previously made choices fixed. This process starts with the first component of the generating vector and 1-dimensional rule is constructed, then the process continues to find the second component for 2-dimensional rule and so on, and in each step the criterion of choice of the components is to minimize the worst-case error. At first, the above technique was developed by the authors in the case when the number of the points of lattice \(n\) is a prime. In the presented paper this algorithm is generalized for an arbitrary \(n\). The component-by-component algorithm is given in the form of matrix-vector product. This matrix-vector product can be done in time of order \(O(n\log(n))\) and requires memory of order \(O(n)\). It is shown that for any positive integer \(n\) the construction of \(s\)-dimensional rank-1 lattice with \(n\) points has a total construction cost of order \(O(sn\log(n))\) and needs memory of order \(O(n)\). Some illustrative examples are given in three cases for the number \(n\) of the points of lattice: when \(n\) is a prime, a prime powers, and for an arbitrary \(n\).