Cools, Ronald; Kuo, Frances Y.; Nuyens, Dirk Constructing embedded lattice rules for multivariate integration. (English) Zbl 1126.65002 SIAM J. Sci. Comput. 28, No. 6, 2162-2188 (2006). Summary: Lattice rules are a family of equal-weight cubature formulae for approximating high-dimensional 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 \(\mathcal O(d n (\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 \(\mathcal O(n^{-1+\delta})\), \(\delta>0\), as those constructed for a fixed number of points, and that the implied constant gains only a factor of 1.30 to 1.55. Cited in 52 Documents MSC: 65C05 Monte Carlo methods 65D32 Numerical quadrature and cubature formulas 41A55 Approximate quadratures 41A63 Multidimensional problems Keywords:numerical integration; quasi-monte Carlo methods; rank-1 lattice rules; fast component-by-component construction; embedded lattice rules; extensible lattice sequences; numerical examples; cubature formulae; algorithm; fast Fourier transforms PDFBibTeX XMLCite \textit{R. Cools} et al., SIAM J. Sci. Comput. 28, No. 6, 2162--2188 (2006; Zbl 1126.65002) Full Text: DOI