Title: Constructing embedded lattice rules for multivariate integration
Authors: Cools, Ronald *
Kuo, Frances Y. *
Nuyens, Dirk * # ×
Issue Date: Dec-2006
Publisher: SIAM, Philadelphia, PA
Series Title: SIAM Journal on Scientific Computing vol:28 issue:16 pages:2162-2188
Abstract: 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 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+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.

ISSN: 1064-8275
Publication status: published
KU Leuven publication type: IT
Appears in Collections:NUMA, Numerical Analysis and Applied Mathematics Section
* (joint) first author
× corresponding author
# (joint) last author

Files in This Item:

There are no files associated with this item.

Request a copy


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science