Constructing embedded lattice rules for multivariate integration

Abstract. Lattice rules are a family of equal-weight cubature formulas for approximating highdimensional integrals. By now it is well established that good generating vectors for lattice rules having n points can be constructed component-by-component for integrands belonging to certain weighted function spaces, and that they can achieve the optimal rate of convergence. Although the lattice rules constructed this way are extensible in dimension, they are not extensible in n, thus when n is changed the generating vector needs to be constructed anew. In this paper we introduce a new algorithm for constructing good generating vectors for embedded lattice rules which can be used for a range of n while still being extensible in dimension. By using an adaptation of the fast component-by-component construction algorithm (which makes use of fast Fourier transforms), we are able to obtain good generating vectors for thousands of dimensions and millions of points, under both product weight and order-dependent weight settings, at the cost of O(dn(log(n)) 2) operations. With a sufficiently large number of points and good overall quality, these embedded lattice rules can be used for practical purposes in the same way as a low-discrepancy sequence. We show for a range of weight settings in an unanchored Sobolev space that our embedded lattice rules achieve the same (optimal) rate of convergence O(n −1+δ), δ> 0, as those constructed for a fixed number of points, and that the implied constant only gains a factor of 1.30 to 1.55. Key words. Numerical integration, Quasi-Monte Carlo methods, Rank-1 lattice rules, Fast component-by-component construction, Embedded lattice rules, Extensible lattice sequences AMS subject classifications. 65D30, 65D32, 68W40 1. Introduction. Integral