Quasi-Monte Carlo methods for numerical integration of multivariate Haar series II

The present paper contains a comparison of different classes of multivariate Haar series that have been studied with respect to numerical integration, new properties ofE _s ^α -classes and numerical results. Research supported by the Austrian Science Foundation (FWF), project no. P11143-MAT.     

Extensible hyperplane nets

Extensible (polynomial) lattice point sets have the property that the number N of points in the node set of a quasi-Monte Carlo algorithm may be increased while retaining the existing points. Explicit constructions for extensible (polynomial) lattice point sets have been presented recently by Niederreiter and Pillichshammer. It is the aim of this paper to establish extensibility for a powerful generalization of polynomial lattice point sets, the so-called hyperplane nets.     

The tent transformation can improve the convergence rate of quasi-Monte Carlo algorithms using digital nets

In this paper we investigate multivariate integration in reproducing kernel Sobolev spaces for which the second partial derivatives are square integrable. As quadrature points for our quasi-Monte Carlo algorithm we use digital (t,m,s)-nets over which are randomly digitally shifted and then folded using the tent transformation. For this QMC algorithm we show that the root mean square worst-case error converges with order for any ɛ > 0, where 2 ^m is the number of points. A similar result for lattice rules has previously been shown by Hickernell. Ligia L. Cristea is supported by the Austrian Research Fund (FWF), Project P 17022-N 12 and Project S 9609. Josef Dick is supported by the Australian Research Council under its Center of Excellence Program. Gunther Leobacher is supported by the Austrian Research Fund (FWF), Project S 8305. Friedrich Pillichshammer is supported by the Austrian Research Fund (FWF), Project P 17022-N 12, Project S 8305 and Project S 9609.     

Quasi-monte carlo methods for numerical integration of multivariate Haar series

In the present paper we study quasi-Monte Carlo methods to integrate functions representable by generalized Haar series in high dimensions. Using (t, m, s)-nets to calculate the quasi-Monte Carlo approximation, we get best possible estimates of the integration error for practically relevant classes of functions. The local structure of the Haar functions yields interesting new aspects in proofs and results. The results are supplemented by concrete computer calculations. Research supported by the Austrian Science Foundation (FWF), project no. P11143-MAT.     

Shifted lattice rules based on a general weighted discrepancy for integrals over Euclidean space

We approximate weighted integrals over Euclidean space by using shifted rank-1 lattice rules with good bounds on the “generalised weighted star discrepancy”. This version of the discrepancy corresponds to the classic L_∞ weighted star discrepancy via a mapping to the unit cube. The weights here are general weights rather than the product weights considered in earlier works on integrals over R^d. Known methods based on an averaging argument are used to show the existence of these lattice rules, while the component-by-component technique is used to construct the generating vector of these shifted lattice rules. We prove that the bound on the weighted star discrepancy considered here is of order O(n^−1+δ) for any δ>0 and with the constant involved independent of the dimension. This convergence rate is better than the O(n^−1/2) achieved so far for both Monte Carlo and quasi-Monte Carlo methods.     

Low discrepancy sequences in high dimensions: How well are their projections distributed?

Quasi-Monte Carlo (QMC) methods have been successfully used to compute high-dimensional integrals arising in many applications, especially in finance. To understand the success and the potential limitation of QMC, this paper focuses on quality measures of point sets in high dimensions. We introduce the order-?$?$, superposition and truncation discrepancies, which measure the quality of selected projections of a point set on lower-dimensional spaces. These measures are more informative than the classical ones. We study their relationships with the integration errors and study the tractability issues. We present efficient algorithms to compute these discrepancies and perform computational investigations to compare the performance of the Sobol’ nets with that of the sets of Latin hypercube sampling and random points. Numerical results show that in high dimensions the superiority of the Sobol’ nets mainly derives from the one-dimensional projections and the projections associated with the earlier dimensions; for order-2 and higher-order projections all these point sets have similar behavior (on the average). In weighted cases with fast decaying weights, the Sobol’ nets have a better performance than the other two point sets. The investigation enables us to better understand the properties of QMC and throws new light on when and why QMC can have a better (or no better) performance than Monte Carlo for multivariate integration in high dimensions.     

Variance bounds and existence results for randomly shifted lattice rules

We study the convergence of the variance for randomly shifted lattice rules for numerical multiple integration over the unit hypercube in an arbitrary number of dimensions. We consider integrands that are square integrable but whose Fourier series are not necessarily absolutely convergent. For such integrands, a bound on the variance is expressed through a certain type of weighted discrepancy. We prove existence and construction results for randomly shifted lattice rules such that the variance bounds are almost O(n^−α)$O\left(n^{-\alpha }\right)$, where n$n$ is the number of function evaluations and α>1$\alpha >1$ depends on our assumptions on the convergence speed of the Fourier coefficients. These results hold for general weights, arbitrary n$n$, and any dimension. With additional conditions on the weights, we obtain a convergence that holds uniformly in the dimension, and this provides sufficient conditions for strong tractability of the integration problem. We also show that lattice rules that satisfy these bounds are not difficult to construct explicitly and we provide numerical illustrations of the behaviour of construction algorithms.     

Compound nonlinear congruential pseudorandom numbers

The nonlinear congruential method for generating uniform pseudorandom numbers has several very promising properties. However, an implementation in multiprecision of these pseudorandom number generators is usually necessary. In the present paper a compound version of the nonlinear congruential method is introduced, which overcomes this disadvantage. It is shown that the generated sequences have very attractive statistical independence properties. The results that are established are essentially best possible and show that the generated pseudorandom numbers model true random numbers very closely. The method of proof relies heavily on a thorough analysis of exponential sums.     

Lower bounds for the discrepancy of triples of inversive congruential pseudorandom numbers with power of two modulus

This paper deals with the inversive congruential method with power of two modulusm for generating uniform pseudorandom numbers. Statistical independence properties of the generated sequences are studied based on the distribution of triples of successive pseudorandom numbers. It is shown that there exist parameters in the inversive congruential method such that the discrepancy of the corresponding point sets in the unit cube is of an order of magnitude at leastm ^–1/3. The method of proof relies on a detailed analysis of certain rational exponential sums.     

General discrepancy estimates III: The Erdös-Turán-Koksma inequality for the Haar function system

The classical Erdös-Turán-Koksma inequality gives us an upper bound for the discrepancy of a sequence in thes-dimensional unit cube in terms of exponential sums, more precisely, in terms of the trigonometric function system.In this paper, we shall prove the inequality of Erdös-Turán-Koksma for the extreme and the star discrepancy, for generalized Haar function systems. Further, we shall show the existence of the inequality of Erdös-Turán-Koksma for the isotropic discrepancy, for generalized Haar and Walsh function systems.Research supported by the Austrian Science Foundation, project no. P9285/TEC.     

On the Distribution of Compound Inversive Congruential Pseudorandom Numbers

 Inversive methods are interesting alternatives to linear methods for pseudorandom number generation. A particularly attractive method is the compound inversive congruential method introduced and analyzed by Huber and Eichenauer-Herrmann. We present the first nontrivial worst-case results on the distribution of sequences of compound inversive congruential pseudorandom numbers in parts of the period. The proofs are based on new bounds for certain exponential sums. (Received 2 March 2000; in revised form 22 November 2000)     

Haar Function Based Estimates of the Star-Discrepancy of Plane Digital Nets

 We apply the Haar function system to estimate the star-discrepancy of special digital (t,m,s)-nets in dimension . We use a basic technique based on discretization combined with an exact calculation of the discrete star-discrepancy. (Received 30 August 1999; in revised form 17 January 2000)     

The Existence of Good Extensible Polynomial Lattice Rules

Extensible (polynomial) lattice rules have been introduced recently and they are convenient tools for quasi-Monte Carlo integration. It is shown in this paper that for suitable infinite families of polynomial moduli there exist generating parameters for extensible rank-1 polynomial lattice rules such that for all these infinitely many moduli and all dimensions s the quantity R ^(s) and the star discrepancy are small. The case of Korobov-type polynomial lattice rules is also considered.Received April 30, 2002; in revised form August 21, 2002 Published online April 4, 2003     

Korobov Spaces with Respect to Digital Orthonormal Bases

 For an orthonormal basis (ONB) of we define classes of functions according to the order of decay of the Fourier coefficients with respect to the considered ONB . The rate is expressed in the real parameter α. We investigate the following problem: What is the order of decay, if any, when we consider with respect to another ONB ? If the function is expressable as an absolutely convergent Fourier series with respect to , we give bounds for the new order of decay, which we call . Special attention is given to digital orthonormal bases (dONBs) of which the Walsh and Haar systems are examples treated in the present paper. Bounding intervals and in several cases explicit values for are given for the case of dONBs. An application to quasi-Monte Carlo numerical integration is mentioned. (Received 21 February 2000; in revised form 19 October 2000)     

Digital nets with infinite digit expansions and construction of folded digital nets for quasi-Monte Carlo integration

In this paper we study quasi-Monte Carlo integration of smooth functions using digital nets. We fold digital nets over ${\mathbb{Z}}_b$ by means of the $b$-adic tent transformation, which has recently been introduced by the authors, and employ such folded digital nets as quadrature points. We first analyze the worst-case error of quasi-Monte Carlo rules using folded digital nets in reproducing kernel Hilbert spaces. Here we need to permit digital nets with “infinite digit expansions”, which are beyond the scope of the classical definition of digital nets. We overcome this issue by considering the infinite product of cyclic groups and the characters on it. We then give an explicit means of constructing good folded digital nets as follows: we use higher order polynomial lattice point sets for digital nets and show that the component-by-component construction can find good folded higher order polynomial lattice rules that achieve the optimal convergence rate of the worst-case error in certain Sobolev spaces of smoothness of arbitrarily high order.     

Discrepancy and the Error in Integration

 This paper is devoted to an estimation of the error of integration with respect to arbitrary unit measures μ and ν on only in terms of continuity or smoothness properties of the function f and the discrepancy . Here, stands for certain classes of (Borel-) test sets. The proofs are in part based on a continuous wavelet analysis of the integrated function by means of Haar-type wavelets. Received 26 January 2001; in revised form 23 September 2001     

Theoretical and empirical convergence results for additive congruential random number generators

Additive Congruential Random Number (ACORN) generators represent an approach to generating uniformly distributed pseudo-random numbers that is straightforward to implement efficiently for arbitrarily large order and modulus; if it is implemented using integer arithmetic, it becomes possible to generate identical sequences on any machine.This paper briefly reviews existing results concerning ACORN generators and relevant theory concerning sequences that are well distributed mod 1 in k dimensions. It then demonstrates some new theoretical results for ACORN generators implemented in integer arithmetic with modulus M=2^μ showing that they are a family of generators that converge (in a sense that is defined in the paper) to being well distributed mod 1 in k dimensions, as μ=log₂M tends to infinity. By increasing k, it is possible to increase without limit the number of dimensions in which the resulting sequences approximate to well distributed.The paper concludes by applying the standard TestU01 test suite to ACORN generators for selected values of the modulus (between 2⁶⁰ and 2¹⁵⁰), the order (between 4 and 30) and various odd seed values. On the basis of these and earlier results, it is recommended that an order of at least 9 be used together with an odd seed and modulus equal to 2^30p, for a small integer value of p. While a choice of p=2 should be adequate for most typical applications, increasing p to 3 or 4 gives a sequence that will consistently pass all the tests in the TestU01 test suite, giving additional confidence in more demanding applications.The results demonstrate that the ACORN generators are a reliable source of uniformly distributed pseudo-random numbers, and that in practice (as suggested by the theoretical convergence results) the quality of the ACORN sequences increases with increasing modulus and order.     

A remark on random and equidistributed sequences

The average of the values of a function f on the points of an equidistributed sequence in [0, 1] ^s converges to the integral of f as soon as f is Riemann integrable. Some known low discrepancy sequences perform faster integration than independent random sampling (cf. [1]). We show that a small random absolutely continuous perturbation of an equidistributed sequence allows to integrate bounded Borel functions, and more generally that, if the law of the random perturbation doesn't charge polar sets, such perturbed sequences allow to integrate bounded quasi-continuous functions.     

Numerical integration with Taylor truncations for the quadrilateral and hexahedral finite elements

For general quadrilateral or hexahedral meshes, the finite-element methods require evaluation of integrals of rational functions, instead of traditional polynomials. It remains as a challenge in mathematics to show the traditional Gauss quadratures would ensure the correct order of approximation for the numerical integration in general. However, in the case of nested refinement, the refined quadrilaterals and hexahedra converge to parallelograms and parallelepipeds, respectively. Based on this observation, the rational functions of inverse Jacobians can be approximated by the Taylor expansion with truncation. Then the Gauss quadrature of exact order can be adopted for the resulting integrals of polynomials, retaining the optimal order approximation of the finite-element methods. A theoretic justification and some numerical verification are provided in the paper.     

Walsh Series Analysis of the L 2-Discrepancyof Symmetrisized Point Sets

 We present a method to estimate the L ₂-discrepancy of symmetrisized point sets from above and from below with the help of Walsh series analysis. We apply the method to a class of two-dimensional net-type point sets, thereby generalizing results of Halton and Zaremba and of Proinov. (Received 14 September 2000)