D. Nuyens and R. Cools. Fast component-by-component construction, a reprise for diﬀerent kernels. In H. Niederreiter and D. Talay, editors, Monte Carlo and Quasi-Monte Carlo Methods 2004, pages 371–385. Springer-Verlag, 2006. Cited on pp. 82, 153, 178. See also Chapter 6 of Dirk’s PhD Thesis.
Let and be the adic expansion of (unique in the sense that infinitely many of the are different from ). We use the notation as in the book. Assume that is a prime number. For the sake of definiteness, consider the mean square worst-case error
where is a polynomial lattice rule, for , and
This criterion does not depend on if or , only on . This does not hold for other values of . In the following we assume that , though the ideas can be generalised to arbitrary bases. We are using the component-by-component algorithm. Assume that are already chosen. Then we define a function of given by
As only depends on for , we can introduce some simplifications. Let . Then we can write
The aim is to find which minimises . Note that only depends on , hence we can also find which minimises
We can simplify further. Using the definition of it follows that the above is equivalent to finding which minimises
where is the smallest integer such that with . Note that for . Let , , and
In this notation we have .
Assume that for an we have
where . Then
where are the polynomials associated with , and the multiplication is carried out in . Thus is the smallest integer such that , where .
For simplicity let us assume that is primitive. Then the monomial is a generating element of the multiplicative group of . Let .
Applying the Rader transform we obtain a circulant matrix
Now is the smallest integer such that . We have
Hence we can simplify the matrix further. Let hence . Then let
where and is the permuted vector . Then we can find as
The calculation of the matrix is simpler because we do not need to calculate the Laurent series expansion of .
The same results hold if is irreducible but not primitive. In this case one has to replace by a generating element of the cyclic multiplicative group of .
We add some further observations:
- The entries in the matrix are from the set . Hence the matrix has only different entries (the total number of entries in is , which is much larger). This was also pointed out in Dirk’s PhD Thesis, p. 150.
- In each row and for each , the entry occurs times. The last statement holds since there are polynomials of degree in .
- All the entries of the matrix are of the form , hence to multiply the vector with we only need to shift the numbers of the vectors digits rather instead of multiplying real numbers. Hence in calculating no multiplication is required.
- Let be the matrix whose entries are all . Then instead of using in the minimisation problem above, one could use . The matrix is then a circulant matrix which has entries which are .
The multiplication is carried out using the fast Fourier transform, which does not take advantage of these observations.
It is not known whether there is an alternative algorithm which calculates in at most operations (and which takes advantage of some of the observations above).