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.     

Reducing the construction cost of the component-by-component construction of good lattice rules

The construction of randomly shifted rank- lattice rules, where the number of points is a prime number, has recently been developed by Sloan, Kuo and Joe for integration of functions in weighted Sobolev spaces and was extended by Kuo and Joe and by Dick to composite numbers. To construct -dimensional rules, the shifts were generated randomly and the generating vectors were constructed component-by-component at a cost of operations. Here we consider the situation where is the product of two distinct prime numbers and . We still generate the shifts randomly but we modify the algorithm so that the cost of constructing the, now two, generating vectors component-by-component is only operations. This reduction in cost allows, in practice, construction of rules with millions of points. The rules constructed again achieve a worst-case strong tractability error bound, with a rate of convergence for 0$">.

     

An equivalence of two constructions of permutation-twisted modules for lattice vertex operator algebras

The problem of constructing twisted modules for a vertex operator algebra and an automorphism has been solved in particular in two contexts. One of these two constructions is that initiated by the third author in the case of a lattice vertex operator algebra and an automorphism arising from an arbitrary lattice isometry. This construction, from a physical point of view, is related to the space–time geometry associated with the lattice in the sense of string theory. The other construction is due to the first author, jointly with C. Dong and G. Mason, in the case of a multifold tensor product of a given vertex operator algebra with itself and a permutation automorphism of the tensor factors. The latter construction is based on a certain change of variables in the worldsheet geometry in the sense of string theory. In the case of a lattice that is the orthogonal direct sum of copies of a given lattice, these two very different constructions can both be carried out, and must produce isomorphic twisted modules, by a theorem of the first author jointly with Dong and Mason. In this paper, we explicitly construct an isomorphism, thereby providing, from both mathematical and physical points of view, a direct link between space–time geometry and worldsheet geometry in this setting.     

An overview of the computational aspects of Kronrod quadrature rules

We present a survey of the computational aspects of Kronrod's rules, and in particular we describe recent results about their construction, error estimates and applications, including new developments that have been suggested by the Kronrod's strategy.     

The number of lattice rules

A lattice rule is a quadrature rule for integration over ans-dimensional hypercube that employsN abscissas located on a lattice, chosen to conform to certain specifications. In this paper we determine the numberv _s(N) of distinctN-points-dimensional lattice rules. We show that, in general,

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.

     

Permutability of rules in lattice theory

Lattice theory with the meet and join operations is formulated as a system of rules of inference. The order of application of these rules can be permuted so that a subterm property follows: If an atomic formula is derivable from given atomic formulas by the rules, it has a derivation all terms of which are terms in the given formulas or the conclusion. A direct decision method for universal formulas in lattice theory with the meet and join operations follows.     

More constructions of pseudorandom sequences of k symbols

We present some new constructions of families of pseudorandom sequences of k symbols, which generalize several previous constructions for the binary case.     

Modified constructions of binary sequences using multiplicative inverse

Two new families of finite binary sequences are constructed using multiplicative inverse. The sequences are shown to have strong pseudorandom properties by using some estimates of certain exponential sums over finite fields. The constructions can be implemented fast since multiplicative inverse over finite fields can be computed in polynomial time.     

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.     

Probabilistic constructions of B 2[g] sequences

We use the probabilistic method to prove that for any positive integer g there exists an infinite B2[g] sequence A = {ak} such that ak ≤ k^2＋1/g（log k）^1/g＋0（1） as k→∞. The exponent 2＋1/g improves the previous one, 2 ＋ 2/g, obtained by Erdos and Renyi in 1960. We obtain a similar result for B2 [g] sequences of squares.     

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.

     

Modular constructions of pseudorandom binary sequences with composite moduli

Summary Recently, Goubin, Mauduit, Rivat and Sárk?zy have given three constructions for large families of binary sequences. In each of these constructions the sequence is defined by modulo <InlineEquation ID=IE"1"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"2"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"3"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"4"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"5"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"6"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"7"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"8"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"9"><EquationSource Format="TEX"><![CDATA[$]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>p$ congruences where $p$ is a prime number. In this paper the three constructions are extended to the case when the modulus is of the form $pq$ where $p$, $q$ are two distinct primes not far apart (note that the well-known Blum-Blum-Shub and RSA constructions for pseudorandom sequences are also of this type). It is shown that these modulo $pq$ constructions also have certain strong pseudorandom properties but, e.g., the (``long range') correlation of order $4$ is large (similar phenomenon may occur in other modulo $pq$ constructions as well).     

Generalized renewal sequences and infinitely divisible lattice distributions

We introduce an increasing set of classes Γ_a (0?α?1) of infinitely divisible (i.d.) distributions on {0,1,2,…}, such that Γ₀ is the set of all compound-geometric distributions and Γ₁ the set of all compound-Poisson distributions, i.e. the set of all i.d. distributions on the non-negative integers. These classes are defined by recursion relations similar to those introduced by Katti [4] for Γ₁ and by Steutel [7] for Γ₀. These relations can be regarded as generalizations of those defining the so-called renewal sequences (cf. [5] and [2]). Several properties of i.d. distributions now appear as special cases of properties of the Γ_a'.     

Triangular canonical forms for lattice rules of prime-power order

In this paper we develop a theory of -cycle representations for -dimensional lattice rules of prime-power order. Of particular interest are canonical forms which, by definition, have a -matrix consisting of the nontrivial invariants. Among these is a family of triangular forms, which, besides being canonical, have the defining property that their -matrix is a column permuted version of a unit upper triangular matrix. Triangular forms may be obtained constructively using sequences of elementary transformations based on elementary matrix algebra. Our main result is to define a unique canonical form for prime-power rules. This ultratriangular form is a triangular form, is easy to recognize, and may be derived in a straightforward manner.

     

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.     

Three- and four-dimensional -optimal lattice rules of moderate trigonometric degree

A systematic search for optimal lattice rules of specified trigonometric degree over the hypercube has been undertaken. The search is restricted to a population of lattice rules . This includes those where the dual lattice may be generated by points for each of which . The underlying theory, which suggests that such a restriction might be helpful, is presented. The general character of the search is described, and, for , and , , a list of -optimal rules is given. It is not known whether these are also optimal rules in the general sense; this matter is discussed.