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     

Construction of a local and global Lyapunov function for discrete dynamical systems using radial basis functions

The basin of attraction of an asymptotically stable fixed point of the discrete dynamical system given by the iteration x_n+1=g(x_n) can be determined through sublevel sets of a Lyapunov function. In Giesl [On the determination of the basin of attraction of discrete dynamical systems. J. Difference Equ. Appl. 13(6) (2007) 523–546] a Lyapunov function is constructed by approximating the solution of a difference equation using radial basis functions. However, the resulting Lyapunov function is non-local, i.e. it has no negative discrete orbital derivative in a neighborhood of the fixed point. In this paper we modify the construction method by using the Taylor polynomial and thus obtain a Lyapunov function with negative discrete orbital derivative both locally and globally.     

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.     

Parallel algorithms for variational inequalities over the Cartesian product of the intersections of the fixed point sets of nonexpansive mappings

This paper presents a framework of iterative algorithms for the variational inequality problem over the Cartesian product of the intersections of the fixed point sets of nonexpansive mappings in real Hilbert spaces. Strong convergence theorems are established under a certain contraction assumption with respect to the weighted maximum norm. The proposed framework produces as a simplest example the hybrid steepest descent method, which has been developed for solving the monotone variational inequality problem over the intersection of the fixed point sets of nonexpansive mappings. An application to a generalized power control problem and numerical examples are demonstrated.     

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.     

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.     

Interpolation lattices in several variables

Principal lattices are classical simplicial configurations of nodes suitable for multivariate polynomial interpolation in n dimensions. A principal lattice can be described as the set of intersection points of n + 1 pencils of parallel hyperplanes. Using a projective point of view, Lee and Phillips extended this situation to n + 1 linear pencils of hyperplanes. In two recent papers, two of us have introduced generalized principal lattices in the plane using cubic pencils. In this paper we analyze the problem in n dimensions, considering polynomial, exponential and trigonometric pencils, which can be combined in different ways to obtain generalized principal lattices.We also consider the case of coincident pencils. An error formula for generalized principal lattices is discussed. Partially supported by the Spanish Research Grant BFM2003-03510, by Gobierno de Aragón and Fondo Social Europeo.     

Higher integrality conditions, volumes and Ehrhart polynomials

A polytope is integral if all of its vertices are lattice points. The constant term of the Ehrhart polynomial of an integral polytope is known to be 1. In previous work, we showed that the coefficients of the Ehrhart polynomial of a lattice-face polytope are volumes of projections of the polytope. We generalize both results by introducing a notion of k-integral polytopes, where 0-integral is equivalent to integral. We show that the Ehrhart polynomial of a k-integral polytope P has the properties that the coefficients in degrees less than or equal to k are determined by a projection of P, and the coefficients in higher degrees are determined by slices of P. A key step of the proof is that under certain generality conditions, the volume of a polytope is equal to the sum of volumes of slices of the polytope.     

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)     

On coefficients of polynomials over finite fields

In this paper we study the relation between coefficients of a polynomial over finite field Fq and the moved elements by the mapping that induces the polynomial. The relation is established by a special system of linear equations. Using this relation we give the lower bound on the number of nonzero coefficients of polynomial that depends on the number m of moved elements. Moreover we show that there exist permutation polynomials of special form that achieve this bound when m|q−1. In the other direction, we show that if the number of moved elements is small then there is an recurrence relation among these coefficients. Using these recurrence relations, we improve the lower bound of nonzero coefficients when m?q−1 and . As a byproduct, we show that the moved elements must satisfy certain polynomial equations if the mapping induces a polynomial such that there are only two nonzero coefficients out of 2m consecutive coefficients. Finally we provide an algorithm to compute the coefficients of the polynomial induced by a given mapping with O(q3/2) operations.     

Some Applications of a Bombieri-Type Theoremin Totally Real Number Fields

 The primary concern of this paper is to present three further applications of a multi-dimensional version of Bombieri’s theorem on primes in arithmetic progressions in the setting of a totally real algebraic number field K. First, we deal with the order of magnitude of a greatest (relative to its norm) prime ideal factor of , where the product runs over prime arguments ω of a given irreducible polynomial F which lie in a certain lattice point region. Then, we turn our attention to the problem about the occurrence of algebraic primes in a polynomial sequence generated by an irreducible polynomial of K with prime arguments. Finally, we give further contributions to the binary Goldbach problem in K. (Received 11 January 2000; in revised form 4 December 2000)     

On the number of lattice points between two enlarged and randomly shifted,copies of an oval

Summary Let A be an oval with a nice boundary in ²,R a large positive number,c>0 some fixed number and a uniformly distributed random vector in the unit square [0,1]². We are interested in the number of lattice points in the shifted annular region consisting of the difference of the sets {(R+c/R)A–} and {(R–c/R)A–}. We prove that whenR tends to infinity, the expectation and the variance of this random variable tend to 4c times the area of the set A, i.e. to the area of the domain where we are counting the number of lattice points. This is consistent with computer studies in the case of a circle or an ellipse which indicate that the distribution of this random variable tends to the Poisson law. We also make some comments about possible generalizations.     

A numerical study of optimized sparse preconditioners

Preconditioning strategies based on incomplete factorizations and polynomial approximations are studied through extensive numerical experiments. We are concerned with the question of the optimal rate of convergence that can be achieved for these classes of preconditioners.Our conclusion is that the well-known Modified Incomplete Cholesky factorization (MIC), cf. e.g., Gustafsson [20], and the polynomial preconditioning based on the Chebyshev polynomials, cf. Johnson, Micchelli and Paul [22], have optimal order of convergence as applied to matrix systems derived by discretization of the Poisson equation. Thus for the discrete two-dimensional Poisson equation withn unknowns,O(n ^1/4) andO(n ^1/2) seem to be the optimal rates of convergence for the Conjugate Gradient (CG) method using incomplete factorizations and polynomial preconditioners, respectively. The results obtained for polynomial preconditioners are in agreement with the basic theory of CG, which implies that such preconditioners can not lead to improvement of the asymptotic convergence rate.By optimizing the preconditioners with respect to certain criteria, we observe a reduction of the number of CG iterations, but the rates of convergence remain unchanged.Supported by The Norwegian Research Council for Science and the Humanities (NAVF) under grants no. 413.90/002 and 412.93/005.Supported by The Royal Norwegian Council for Scientific and Industrial Research (NTNF) through program no. STP.28402: Toolkits in industrial mathematics.     

Eine explizite Abschätzung für die Gitter-Diskrepanz von Rotationsellipsoiden

An explicit estimate for the lattice point discrepancy of ellipsoids of rotation. For the lattice point discrepancy (i.e., the number of integer points minus the volume) of the ellipsoid (u ₁ ² + u ₂ ²)/a + a ² u ₃ ² ≤ x (a, x > 0), this paper provides an estimate of the form terms of smaller order in x. Die Autoren danken dem ?sterreichischen Fonds zur F?rderung der wissenschaftlichen Forschung (FWF) für finanzielle Unterstützung unter der Projekt-Nr. P18079-N12.     

Quantitative recurrence properties for beta-dynamical system

This note is concerned with the quantitative recurrence properties of beta dynamical system ([0,1],Tβ) for general β>1; the size of points with the prescribed recurrence rate is determined. More precisely, Hausdorff dimensions of the sets and are obtained completely, where ψ is a positive function defined on N and f is a positive continuous function on [0,1]. Besides, the pressure function P(f,Tβ) with a continuous potential f is proven to be continuous with respect to β.     

Construction algorithms for higher order polynomial lattice rules

Higher order polynomial lattice point sets are special types of digital higher order nets which are known to achieve almost optimal convergence rates when used in a quasi-Monte Carlo algorithm to approximate high-dimensional integrals over the unit cube. The existence of higher order polynomial lattice point sets of “good” quality has recently been established, but their construction was not addressed.We use a component-by-component approach to construct higher order polynomial lattice rules achieving optimal convergence rates for functions of arbitrarily high smoothness and at the same time–under certain conditions on the weights–(strong) polynomial tractability. Combining this approach with a sieve-type algorithm yields higher order polynomial lattice rules adjusting themselves to the smoothness of the integrand up to a certain given degree. Higher order Korobov polynomial lattice rules achieve analogous results.     

A new non‐polynomial univariate interpolation formula of Hermite type

A new C ^∞ interpolant is presented for the univariate Hermite interpolation problem. It differs from the classical solution in that the interpolant is of non‐polynomial nature. Its basis functions are a set of simple, compact support, transcendental functions. The interpolant can be regarded as a truncated Multipoint Taylor series. It has essential singularities at the sample points, but is well behaved over the real axis and satisfies the given functional data. The interpolant converges to the underlying real‐analytic function when (i) the number of derivatives at each point tends to infinity and the number of sample points remains finite, and when (ii) the spacing between sample points tends to zero and the number of specified derivatives at each sample point remains finite. A comparison is made between the numerical results achieved with the new method and those obtained with polynomial Hermite interpolation. In contrast with the classical polynomial solution, the new interpolant does not suffer from any ill conditioning, so it is always numerically stable. In addition, it is a much more computationally efficient method than the polynomial approach. This revised version was published online in June 2006 with corrections to the Cover Date.     

Alternating proximal algorithms for linearly constrained variational inequalities: Application to domain decomposition for PDE’s

Let X,Y,Z be real Hilbert spaces, let f:X→R∪{+∞}, g:Y→R∪{+∞} be closed convex functions and let A:X→Z, B:Y→Z be linear continuous operators. Let us consider the constrained minimization problem Given a sequence (γ_n) which tends toward 0 as n→+∞, we study the following alternating proximal algorithm where α and ν are positive parameters. It is shown that if the sequence (γ_n) tends moderately slowly toward 0, then the iterates of (A) weakly converge toward a solution of (P). The study is extended to the setting of maximal monotone operators, for which a general ergodic convergence result is obtained. Applications are given in the area of domain decomposition for PDE’s.     

Baryzentrische Formeln zur Trigonometrischen Interpolation (I)

Summary Barycentric formulas for the interpolation of a periodic functionf by a trigonometric polynomial have been given by Salzer [11] in the case of an odd number of arbitrary (interpolating) points and by Henrici [7] in the special case of equidistant points. We present here formulas for the interpolation with an even number of arbitrary points as well as simpler versions for an even or an odd functionf.

Der Autor dankt Dr. M. H. Gutknecht und Prof. P. Henrici, ohne welche diese Arbeit vielleicht nicht entstanden wäre.