In this post I describe an approach for constructing lattice rules which might be useful for integration in The aim is to use the main ideas from the construction of digital nets over , see here, and apply them to lattice rules. This is the first project mentioned here.
Let us first briefly describe what a lattice rule is. Let be natural numbers and let be an integer vector. For nonnegative real numbers we denote by the fractional part of that is, we have Here denotes the largest integer smaller or equal to For vectors we use this approach component-wise.
Let be natural numbers and let be an integer vector. Let be a function. A lattice rule is a quadrature rule of the form
A lattice rule is useful to approximate the integral Background on lattice rules can be found in Sloan & Joe, Lattice methods for multiple integration, Oxford, 1994 and Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods, SIAM, 1992.
Lattice rules for
In practice the integral one needs to approximate are usually defined on rather than One can use some transformation to transform an integral to an integral It is often not clear what transformation one should use and the quality of the approximation can depend a lot on a good choice of the transformation.
In order to avoid finding a transformation, we aim to find a `lattice rule type construction` which are constructed in As for the digital net case, the final point set in is not a classical lattice anymore. We want the point set to have a local structure, i.e., in certain subintervals of we basically have a classical shifted lattice rule and at the same time the whole point set should have a global structure. The goal is then to approximate the integral by a quadrature rule of the form
A first idea
The first approach to constructing lattice rules in would be analogous to the digital net case, see the post on Quasi-Monte Carlo rules on This requires several steps:
- First we need to solve the one-dimensional problem. Let and let denote its Fourier transform. We need some assumptions on the integrand. The integrand itself needs to go to zero fast enough as Further, the Fourier transform needs to go to zero fast enough as Finally, the derivative of the integrand needs to go to zero as These three assumptions should be used to give us some idea on how to construct the points in the one-dimensional case. Tilings of the phase plane are likely to be useful for this step (some useful ideas on tilings might be here or in the references in this paper).
- The first step should yield points for each coordinate Next we construct points in in the following way. Let be the generating vector for a lattice rule. For each we define the point by
One question is then to ask what structure such a point set has. Are there cases where one obtains shifted lattice rules again in some subcubes of This would be a useful property to have. The weights should then be chosen such that constant functions are integrated exactly in such subcubes.
- Find a criterion for the generating vector of the lattice rule and introduce a construction algorithm for such lattice rules. Alternatively one could just use a generating vector constructed for Korobov lattice rules.
- Prove error bounds for the integration error.
Whether this approach is feasible is currently not known. Any comments and suggestions are welcome.