Construction algorithms for polynomial lattice rules for multivariate integration

We introduce a new construction algorithm for digital nets for integration in certain weighted tensor product Hilbert spaces. The first weighted Hilbert space we consider is based on Walsh functions. Dick and Pillichshammer calculated the worst-case error for integration using digital nets for this space. Here we extend this result to a special construction method for digital nets based on polynomials over finite fields. This result allows us to find polynomials which yield a small worst-case error by computer search. We prove an upper bound on the worst-case error for digital nets obtained by such a search algorithm which shows that the convergence rate is best possible and that strong tractability holds under some condition on the weights.

We extend the results for the weighted Hilbert space based on Walsh functions to weighted Sobolev spaces. In this case we use randomly digitally shifted digital nets. The construction principle is the same as before, only the worst-case error is slightly different. Again digital nets obtained from our search algorithm yield a worst-case error achieving the optimal rate of convergence and as before strong tractability holds under some condition on the weights. These results show that such a construction of digital nets yields the until now best known results of this kind and that our construction methods are comparable to the construction methods known for lattice rules.

We conclude the article with numerical results comparing the expected worst-case error for randomly digitally shifted digital nets with those for randomly shifted lattice rules.

     

Extremal lattices and the construction of lattice rules

After introducing the concept of extremal lattices we show how these can be used to construct lattice rules of a high trigonometric degree.     

An application of Diophantine approximation to the construction of rank-1 lattice quadrature rules

Lattice quadrature rules were introduced by Frolov (1977), Sloan (1985) and Sloan and Kachoyan (1987). They are quasi-Monte Carlo rules for the approximation of integrals over the unit cube in and are generalizations of `number-theoretic' rules introduced by Korobov (1959) and Hlawka (1962)---themselves generalizations, in a sense, of rectangle rules for approximating one-dimensional integrals, and trapezoidal rules for periodic integrands. Error bounds for rank-1 rules are known for a variety of classes of integrands. For periodic integrands with unit period in each variable, these bounds are conveniently characterized by the figure of merit , which was originally introduced in the context of number-theoretic rules. The problem of finding good rules of order (that is, having nodes) then becomes that of finding rules with large values of . This paper presents a new approach, based on the theory of simultaneous Diophantine approximation, which uses a generalized continued fraction algorithm to construct rank-1 rules of high order.

     

The construction of good extensible rank-1 lattices

It has been shown by Hickernell and Niederreiter that there exist generating vectors for integration lattices which yield small integration errors for for all integers . This paper provides algorithms for the construction of generating vectors which are finitely extensible for for all integers . The proofs which show that our algorithms yield good extensible rank-1 lattices are based on a sieve principle. Particularly fast algorithms are obtained by using the fast component-by-component construction of Nuyens and Cools. Analogous results are presented for generating vectors with small weighted star discrepancy.

     

Fast algorithms for component-by-component construction of rank- lattice rules in shift-invariant reproducing kernel Hilbert spaces

We reformulate the original component-by-component algorithm for rank- lattices in a matrix-vector notation so as to highlight its structural properties. For function spaces similar to a weighted Korobov space, we derive a technique which has construction cost , in contrast with the original algorithm which has construction cost . Herein is the number of dimensions and the number of points (taken prime). In contrast to other approaches to speed up construction, our fast algorithm computes exactly the same quantity as the original algorithm. The presented algorithm can also be used to construct randomly shifted lattice rules in weighted Sobolev spaces.

     

Determination of the rank of an integration lattice

The continuing and widespread use of lattice rules for high-dimensional numerical quadrature is driving the development of a rich and detailed theory. Part of this theory is devoted to computer searches for rules, appropriate to particular situations. In some applications, one is interested in obtaining the (lattice) rank of a lattice rule Q(Λ) directly from the elements of a generator matrix B (possibly in upper triangular lattice form) of the corresponding dual lattice Λ^⊥. We treat this problem in detail, demonstrating the connections between this (lattice) rank and the conventional matrix rank deficiency of modulo p versions of B. AMS subject classification (2000) 65D30     

Component-by-component construction of good lattice rules

This paper provides a novel approach to the construction of good lattice rules for the integration of Korobov classes of periodic functions over the unit -dimensional cube. Theorems are proved which justify the construction of good lattice rules one component at a time - that is, the lattice rule for dimension is obtained from the rule for dimension by searching over all possible choices of the th component, while keeping all the existing components unchanged. The construction, which goes against accepted wisdom, is illustrated by numerical examples. The construction is particularly useful if the components of the integrand are ordered, in the sense that the first component is more important than the second, and so on.

     

Four-dimensional lattice rules generated by skew-circulant matrices

We introduce the class of skew-circulant lattice rules. These are -dimensional lattice rules that may be generated by the rows of an skew-circulant matrix. (This is a minor variant of the familiar circulant matrix.) We present briefly some of the underlying theory of these matrices and rules. We are particularly interested in finding rules of specified trigonometric degree . We describe some of the results of computer-based searches for optimal four-dimensional skew-circulant rules. Besides determining optimal rules for we have constructed an infinite sequence of rules that has a limit rho index of . This index is an efficiency measure, which cannot exceed 1, and is inversely proportional to the abscissa count.

     

An overview of fast component-by-component constructions of lattice rules and lattice sequences

Since the initial work by I. H. Sloan and his collaborators on the component-by-component construction of good lattice rules for the approximation of multivariate integrals, a lot of variations on this theme have been published. These include various function spaces, prime and composite number of points, intermediate-rank rules, polynomial lattice rules and extensible rules. We sketch the different variations and discuss the properties needed to have a fast component-by-component construction. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Existence and construction of shifted lattice rules with an arbitrary number of points and bounded weighted star discrepancy for general decreasing weights

We study the problem of constructing shifted rank-1 lattice rules for the approximation of high-dimensional integrals with a low weighted star discrepancy, for classes of functions having bounded weighted variation, where the weighted variation is defined as the weighted sum of Hardy–Krause variations over all lower-dimensional projections of the integrand. Under general conditions on the weights, we prove the existence of rank-1 lattice rules such that for any δ>0, the general weighted star discrepancy is O(n^−1+δ) for any number of points n>1 (not necessarily prime), any shift of the lattice, general (decreasing) weights, and uniformly in the dimension. We also show that these rules can be constructed by a component-by-component strategy. This implies in particular that a single infinite-dimensional generating vector can be used for integrals in any number of dimensions, and even for infinite-dimensional integrands when they have bounded weighted variation. These same lattices are also good with respect to the worst-case error in weighted Korobov spaces with the same types of general weights. Similar results were already available for various special cases, such as general weights and prime n, or arbitrary n and product weights, but not for the most general combination of n composite, general weights, arbitrary shift, and star discrepancy, considered here. Our results imply tractability or strong tractability of integration for classes of integrands with finite weighted variation when the weights satisfy the conditions we give. These classes are a strict superset of those covered by earlier sufficient tractability conditions.     

Quasi-Monte Carlo integration over

In this paper we show that a wide class of integrals over with a probability weight function can be evaluated using a quasi-Monte Carlo algorithm based on a proper decomposition of the domain and arranging low discrepancy points over a series of hierarchical hypercubes. For certain classes of power/exponential decaying weights the algorithm is of optimal order.

     

Good lattice rules based on the general weighted star discrepancy

We study the problem of constructing rank- lattice rules which have good bounds on the ``weighted star discrepancy'. Here the non-negative weights are general weights rather than the product weights considered in most earlier works. In order to show the existence of such good lattice rules, we use an averaging argument, and a similar argument is used later to prove that these lattice rules may be obtained using a component-by-component (CBC) construction of the generating vector. Under appropriate conditions on the weights, these lattice rules satisfy strong tractability bounds on the weighted star discrepancy. Particular classes of weights known as ``order-dependent' and ``finite-order' weights are then considered and we show that the cost of the construction can be very much reduced for these two classes of weights.

     

Efficient calculation of the worst-case error and (fast) component-by-component construction of higher order polynomial lattice rules

We show how to obtain a fast component-by-component construction algorithm for higher order polynomial lattice rules. Such rules are useful for multivariate quadrature of high-dimensional smooth functions over the unit cube as they achieve the near optimal order of convergence. The main problem addressed in this paper is to find an efficient way of computing the worst-case error. A general algorithm is presented and explicit expressions for base 2 are given. To obtain an efficient component-by-component construction algorithm we exploit the structure of the underlying cyclic group. We compare our new higher order multivariate quadrature rules to existing quadrature rules based on higher order digital nets by computing their worst-case error. These numerical results show that the higher order polynomial lattice rules improve upon the known constructions of quasi-Monte Carlo rules based on higher order digital nets.     

Strong tractability of multivariate integration of arbitrary high order using digitally shifted polynomial lattice rules

In this paper we prove the existence of digitally shifted polynomial lattice rules which achieve strong tractability results for Sobolev spaces of arbitrary high smoothness. The convergence rate is shown to be the best possible up to a given degree of smoothness of the integrand. Indeed we even show the existence of polynomial lattice rules which automatically adjust themselves to the smoothness of the integrand up to a certain given degree.Further we show that strong tractability under certain conditions on the weights can be obtained and that polynomial lattice rules exist for which the worst-case error can be bounded independently of the dimension. These results hold independent of the smoothness.     

Good Lattice Rules in Weighted Korobov Spaces with General Weights

We study the problem of multivariate integration and the construction of good lattice rules in weighted Korobov spaces with general weights. These spaces are not necessarily tensor products of spaces of univariate functions. Sufficient conditions for tractability and strong tractability of multivariate integration in such weighted function spaces are found. These conditions are also necessary if the weights are such that the reproducing kernel of the weighted Korobov space is pointwise non-negative. The existence of a lattice rule which achieves the nearly optimal convergence order is proven. A component-by-component (CBC) algorithm that constructs good lattice rules is presented. The resulting lattice rules achieve tractability or strong tractability error bounds and achieve nearly optimal convergence order for suitably decaying weights. We also study special weights such as finite-order and order-dependent weights. For these special weights, the cost of the CBC algorithm is polynomial. Numerical computations show that the lattice rules constructed by the CBC algorithm give much smaller worst-case errors than the mean worst-case errors over all quasi-Monte Carlo rules or over all lattice rules, and generally smaller worst-case errors than the best Korobov lattice rules in dimensions up to hundreds. Numerical results are provided to illustrate the efficiency of CBC lattice rules and Korobov lattice rules (with suitably chosen weights), in particular for high-dimensional finance problems.     

Efficient lattice assessment for LCG and GLP parameter searches

In the present paper we show how to speed up lattice parameter searches for Monte Carlo and quasi-Monte Carlo node sets. The classical measure for such parameter searches is the spectral test which is based on a calculation of the shortest nonzero vector in a lattice. Instead of the shortest vector we apply an approximation given by the LLL algorithm for lattice basis reduction. We empirically demonstrate the speed-up and the quality loss obtained by the LLL reduction, and we present important applications for parameter selections.