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.     

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.

     

Automorphisms of the lattice of classes; perfect thin classes and anc degrees

classes are important to the logical analysis of many parts of mathematics. The classes form a lattice. As with the lattice of computably enumerable sets, it is natural to explore the relationship between this lattice and the Turing degrees. We focus on an analog of maximality, or more precisely, hyperhypersimplicity, namely the notion of a thin class. We prove a number of results relating automorphisms, invariance, and thin classes. Our main results are an analog of Martin's work on hyperhypersimple sets and high degrees, using thin classes and anc degrees, and an analog of Soare's work demonstrating that maximal sets form an orbit. In particular, we show that the collection of perfect thin classes (a notion which is definable in the lattice of classes) forms an orbit in the lattice of classes; and a degree is anc iff it contains a perfect thin class. Hence the class of anc degrees is an invariant class for the lattice of classes. We remark that the automorphism result is proven via a automorphism, and demonstrate that this complexity is necessary.

     

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.     

Comments about the Steinhaus tiling problem

Recently, using Fourier transform methods, it was shown that there is no measurable Steinhaus set in , a set which no matter how translated and rotated contains exactly one integer lattice point. Here, we show that this argument cannot generalize to any lattice and, on the other hand, give some lattices to which this method applies. We also show there is no measurable Steinhaus set for a special honeycomb lattice, the standard tetrahedral lattice in

     

On the complexity of stochastic integration

We study the complexity of approximating stochastic integrals with error for various classes of functions. For Ito integration, we show that the complexity is of order , even for classes of very smooth functions. The lower bound is obtained by showing that Ito integration is not easier than Lebesgue integration in the average case setting with the Wiener measure. The upper bound is obtained by the Milstein algorithm, which is almost optimal in the considered classes of functions. The Milstein algorithm uses the values of the Brownian motion and the integrand. It is bilinear in these values and is very easy to implement. For Stratonovich integration, we show that the complexity depends on the smoothness of the integrand and may be much smaller than the complexity of Ito integration.

     

Anti-Szego quadrature rules

Szego quadrature rules are discretization methods for approximating integrals of the form . This paper presents a new class of discretization methods, which we refer to as anti-Szego quadrature rules. Anti-Szego rules can be used to estimate the error in Szego quadrature rules: under suitable conditions, pairs of associated Szego and anti-Szego quadrature rules provide upper and lower bounds for the value of the given integral. The construction of anti-Szego quadrature rules is almost identical to that of Szego quadrature rules in that pairs of associated Szego and anti-Szego rules differ only in the choice of a parameter of unit modulus. Several examples of Szego and anti-Szego quadrature rule pairs are presented.

     

Infinite-Dimensional Integration in Weighted Hilbert Spaces: Anchored Decompositions,Optimal Deterministic Algorithms,and Higher-Order Convergence

We study the numerical integration of functions depending on an infinite number of variables. We provide lower error bounds for general deterministic algorithms and provide matching upper error bounds with the help of suitable multilevel algorithms and changing-dimension algorithms. More precisely, the spaces of integrands we consider are weighted, reproducing kernel Hilbert spaces with norms induced by an underlying anchored function space decomposition. Here the weights model the relative importance of different groups of variables. The error criterion used is the deterministic worst-case error. We study two cost models for function evaluations that depend on the number of active variables of the chosen sample points, and we study two classes of weights, namely product and order-dependent weights and the newly introduced finite projective dimension weights. We show for these classes of weights that multilevel algorithms achieve the optimal rate of convergence in the first cost model while changing-dimension algorithms achieve the optimal convergence rate in the second model. As an illustrative example, we discuss the anchored Sobolev space with smoothness parameter \(\alpha \) and provide new optimal quasi-Monte Carlo multilevel algorithms and quasi-Monte Carlo changing-dimension algorithms based on higher-order polynomial lattice rules.     

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.

     

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.

     

On the step-by-step construction of quasi-Monte Carlo integration rules that achieve strong tractability error bounds in weighted Sobolev spaces

We develop and justify an algorithm for the construction of quasi-Monte Carlo (QMC) rules for integration in weighted Sobolev spaces; the rules so constructed are shifted rank-1 lattice rules. The parameters characterising the shifted lattice rule are found ``component-by-component': the ()-th component of the generator vector and the shift are obtained by successive -dimensional searches, with the previous components kept unchanged. The rules constructed in this way are shown to achieve a strong tractability error bound in weighted Sobolev spaces. A search for -point rules with prime and all dimensions 1 to requires a total cost of operations. This may be reduced to operations at the expense of storage. Numerical values of parameters and worst-case errors are given for dimensions up to 40 and up to a few thousand. The worst-case errors for these rules are found to be much smaller than the theoretical bounds.

     

On the classification of full factors of type III

We introduce a new invariant for type III factors with no almost-periodic weights. We compute this invariant for certain free Araki-Woods factors. We show that Connes' invariant cannot distinguish all isomorphism classes of free Araki-Woods factors. We show that there exists a continuum of mutually non-isomorphic free Araki-Woods factors, each without almost-periodic weights.

     

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.

     

Better saddlepoint confidence intervals via bootstrap calibration

Confidence interval construction for parameters of lattice distributions is considered. By using saddlepoint formulas and bootstrap calibration, we obtain relatively short intervals and bounds with coverage errors, in contrast with and coverage errors for normal theory intervals and bounds when the population distribution is absolutely continuous. Closed form solutions are also provided for the cases of binomial and Poisson distributions. The method is illustrated by some simulation results.

     

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.

     

Non-crossing partition lattices in finite real reflection groups

For a finite real reflection group with Coxeter element we give a case-free proof that the closed interval, , forms a lattice in the partial order on induced by reflection length. Key to this is the construction of an isomorphic lattice of spherical simplicial complexes. We also prove that the greatest element in this latter lattice embeds in the type simplicial generalised associahedron, and we use this fact to give a new proof that the geometric realisation of this associahedron is a sphere.

     

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.     

Integral points on elliptic curves and -torsion in class groups

We give new bounds for the number of integral points on elliptic curves. The method may be said to interpolate between approaches via diophantine techniques and methods based on quasi-orthogonality in the Mordell-Weil lattice. We apply our results to break previous bounds on the number of elliptic curves of given conductor and the size of the -torsion part of the class group of a quadratic field. The same ideas can be used to count rational points on curves of higher genus.

     

Cycles representing the Todd class of a toric variety

In this paper, we describe a way to construct cycles which represent the Todd class of a toric variety. Given a lattice with an inner product, we assign a rational number to each rational polyhedral cone in the lattice, such that for any toric variety with fan in the lattice, we have

This constitutes an improved answer to an old question of Danilov.

In a similar way, beginning from the choice of a complete flag in the lattice, we obtain the cycle Todd classes constructed by Morelli.

Our construction is based on an intersection product on cycles of a simplicial toric variety developed by the second author. Important properties of the construction are established by showing a connection to the canonical representation of the Todd class of a simplicial toric variety as a product of torus-invariant divisors developed by the first author.

     

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.