Lattice rule generating vectors
This page contains some generating vectors for rank-1 lattice rules.
They were constructed using the component-by-component algorithms (a.k.a. CBC algorithms)
by minimizing as much as possible the shift-averaged worst case errors
in weighted unanchored Sobolev spaces.
Here is a (biased) selection of milestone papers:
- I. H. Sloan and H. Wozniakowski, When are quasi-Monte Carlo
algorithms efficient for high dimensional integrals?, J. Complexity,
14, 1 - 33 (1998).
- I. H. Sloan, F. Y. Kuo, and S. Joe, Constructing randomly shifted
lattice rules in weighted Sobolev spaces, SIAM J. Numer. Anal., 40, 1650 - 1665 (2002).
- F. Y. Kuo, Component-by-component constructions achieve the optimal rate of
convergence for multivariate integration in weighted Korobov and Sobolev spaces,
J. Complexity, 19, 301 - 320 (2003).
- D. Nuyens and R. Cools, Fast algorithms for component-by-component construction
of rank-1 lattice rules in shift-invariant reproducing kernel
Hilbert spaces, Math. Comp., 75, 903 - 920 (2006).
- R. Cools, F. Y. Kuo, D. Nuyens, Constructing embedded lattice rules for multivariate
integration, SIAM J. Sci. Comput., 28, 2162 - 2188 (2006).
Link to article.
For various choices of weights, we provide generating vectors for
fixed lattice rules (i.e., the number of points n is fixed) as
well as embedded/extensible lattice rules
(i.e., the number of points n can be chosen from a range).
Let z = (z1, z2, ..., zd)
denote the generating vector.
For a fixed lattice rule with n points, we have the simple formula
-
the j-th component of the i-th point = frac( i/n * zj )
for i = 0,1,...,n-1 and j = 1,2,...,d,
where frac(.) means taking the fractional part, e.g., frac(1.8) = 0.8.
For an extensible lattice rule, it is also fine to use the above simple formula
provided that the TOTAL NUMBER OF POINTS IS AN EXACT POWER OF 2.
Otherwise a more complicated radical inverse or gray code ordering should be used.
Note that all these lattice rules are designed to be used with random
shifts.
See [5, Section 2.2] for an overview of different types of weights,
see [5, Section 5.1] for a discussion on using lattice points as an extensible
sequence, and
see [5, Section 5.2] regarding error estimation using random shifts.
A collection of generating vectors
Each file in the table below contains two columns: the dimension and the
corresponding component of the generating vector.
The files are named in one of the following two forms:
- lattice-2xxxx-n.d
- lattice-3xxxx-n1-n2.d
The first denotes a fixed lattice rule with n points, while
the second denotes an extensible lattice rule with n taking any
value between n1 and n2.
The xxxx is a code distinguishing different choices of weights. The value d
specifies the number of available components in the file.
In theory, the CBC algorithm can be used to construct generating
vectors up to any dimension.
However, it has been observed that the components start to repeat from
some dimension onward for product-type weights, hence leading to a practical
limit on the value of d. This side effect of the CBC algorithm is yet to
be fully understood.
RECOMMENDATIONS: If you are unsure which lattice rules to try, you may begin
with the following four extensible lattice rules:
- lattice-32001-1024-1048576.3600
(order-2 weights)
- lattice-33002-1024-1048576.9125
(order-3 weights)
- lattice-38005-1024-1048576.5000
(equal product weights)
- lattice-39101-1024-1048576.3600
(decaying product weights)
The error for an extensible lattice rule is at most 1.6 times that of
a fixed lattice rule.
Questions or comments?
We are always keen to hear from you regarding your experience with these
generating vectors.
Please email Frances Kuo <f.kuo@unsw.edu.au>.
Last updated: 20 December 2007