On an example of finite hybrid quasi-Monte Carlo point sets

In this paper, we consider finite hybrid point sets in the unit cube. The components of these stem from two well known types of low discrepancy point sets, namely Hammersley point sets on the one hand, and lattice point sets in the sense of Korobov and Hlawka on the other hand. As a quality measure, we consider the star discrepancy, which gives information about the quality of distribution of finite or infinite sequences. We present existence results for finite hybrid point sets with low discrepancy. Thereby, we make analogous results for infinite sequences more explicit in the sense that, theoretically, it is now possible to find such finite hybrid low discrepancy point sets.     

Tractability properties of the weighted star discrepancy

Tractability properties of various notions of discrepancy have been intensively studied in the last decade. In this paper we consider the so-called weighted star discrepancy which was introduced by Sloan and Wo?niakowski. We show that under a very mild condition on the weights one can obtain tractability with s$s$-exponent zero (s$s$ is the dimension of the point set). In the case of product weights we give a condition such that the weighted star discrepancy is even strongly tractable. Furthermore, we give a lower bound for the weighted star discrepancy for a large class of weights. This bound shows that for such weights one cannot obtain strong tractability.     

Unstable directions and fractal dimension for skew products with overlaps in fibers

A unique feature of smooth hyperbolic non-invertible maps is that of having different unstable directions corresponding to different prehistories of the same point. In this paper we construct a new class of examples of non-invertible hyperbolic skew products with thick fibers for which we prove that there exist uncountably many points in the locally maximal invariant set ?? (actually a Cantor set in each fiber), having different unstable directions corresponding to different prehistories; also we estimate the angle between such unstable directions. We discuss then the Hausdorff dimension of the fibers of ?? for these maps by employing the thickness of Cantor sets, the inverse pressure, and also by use of continuous bounds for the preimage counting function. We prove that in certain examples, there are uncountably many points in ?? with two preimages belonging to ??, as well as uncountably many points having only one preimage in ??. In the end we give examples which, also from the point of view of Hausdorff dimension, are far from being homeomorphisms on ??, as well as far from being constant-to-1 maps on ??.     

Algorithmic construction of low-discrepancy point sets via dependent randomized rounding

We provide a deterministic algorithm that constructs small point sets exhibiting a low star discrepancy. The algorithm is based on recent results on randomized roundings respecting hard constraints and their derandomization. It is structurally much simpler than a previous algorithm presented for this problem in [B. Doerr, M. Gnewuch, A. Srivastav, Bounds and constructions for the star discrepancy via δ$\delta$-covers, J. Complexity, 21 (2005) 691–709]. Besides leading to better theoretical running time bounds, our approach also can be implemented with reasonable effort. We implemented this algorithm and performed numerical comparisons with other known low-discrepancy constructions. The experiments take place in dimensions ranging from 5 to 21 and indicate that our algorithm leads to superior results if the dimension is relatively high and the number of points that have to be constructed is rather small.     

Constructions of general polynomial lattice rules based on the weighted star discrepancy

In this paper we study construction algorithms for polynomial lattice rules modulo arbitrary polynomials. Polynomial lattice rules are a special class of digital nets which yield well distributed point sets in the unit cube for numerical integration.Niederreiter obtained an existence result for polynomial lattice rules modulo arbitrary polynomials for which the underlying point set has a small star discrepancy and recently Dick, Leobacher and Pillichshammer introduced construction algorithms for polynomial lattice rules modulo an irreducible polynomial for which the underlying point set has a small (weighted) star discrepancy.In this work we provide construction algorithms for polynomial lattice rules modulo arbitrary polynomials, thereby generalizing the previously obtained results. More precisely we use a component-by-component algorithm and a Korobov-type algorithm. We show how the search space of the Korobov-type algorithm can be reduced without sacrificing the convergence rate, hence this algorithm is particularly fast. Our findings are based on a detailed analysis of quantities closely related to the (weighted) star discrepancy.     

Average equidistribution and statistical independence properties of digital inversive pseudorandom numbers over parts of the period

This article deals with the digital inversive method for generating uniform pseudorandom numbers. Equidistribution and statistical independence properties of the generated pseudorandom number sequences over parts of the period are studied based on the distribution of tuples of successive terms in the sequence. The main result is an upper bound for the average value of the star discrepancy of the corresponding point sets. Additionally, lower bounds for the star discrepancy are established. The method of proof relies on bounds for exponential sums.

     

A thorough analysis of the discrepancy of shifted Hammersley and van der Corput point sets

We study the star discrepancy of Hammersley nets and van der Corput sequences which are important examples of low-dimensional quasi-Monte Carlo point sets. By a so-called digital shift, the quality of distribution of these point sets can be improved. In this paper, we advance and extend existing bounds on digitally shifted Hammersley and van der Corput point sets and establish criteria for the choice of digital shifts leading to optimal results. Our investigations are partly based on a close analysis of certain sums of distances to the nearest integer. Mathematics Subject Classi cation (2000) 11K38; 11K09     

An Algorithm to Compute Bounds for the Star Discrepancy

We propose an algorithm to compute upper and lower bounds for the star discrepancy of an arbitrary sequence of points in the s-dimensional unit cube. The method is based on a particular partition of the unit cube into subintervals and on a specialized procedure for orthogonal range counting. The cardinality of the partition depends on the dimension and on an accuracy parameter that has to be specified. We have implemented this method and here we present results of some computational experiments obtained with this implementation.     

Linear estimates of accuracy for approximate solutions of inverse problems

In this paper, we explore the question of which non-linear inverse problems, which are solved by a selected regularization method, may have so-called linear a priori accuracy estimates – that is, the accuracy of corresponding approximate solutions linearly depends on the error level of the data. In particular, we prove that if such a linear estimate exists, then the inverse problem under consideration is well posed, according to Tikhonov. For linear inverse problems, we find that the existence of linear estimates lead to, under some assumptions, the well-posedness (according to Tikhonov) on the whole space of solutions. Moreover, we consider a method for solving inverse problems with guaranteed linear estimates, called the residual method on the correctness set (RMCS). The linear a priori estimates of absolute and relative accuracy for the RMCS are presented, as well as analogous a posteriori estimates. A numerical illustration of obtaining linear a priori estimates for appropriate parametric sets of solutions using RMCS is given in comparison with Tikhonov regularization. The a posteriori estimates are calculated on these parametric sets as well.     

New star discrepancy bounds for (t,m,s)-nets and (t,s)-sequences

In this paper, we derive new general upper bounds on the star discrepancy of $(t,m,s)$ -nets and $(t,s)$ -sequences. These kinds of point sets are among the most widely used in quasi-Monte Carlo methods for numerical integration. By our new results, we improve on previous discrepancy bounds and prove a conjecture stated by the second author in an earlier paper.     

Dirichlet–Neumann inverse spectral problem for a star graph of Stieltjes strings

We solve two inverse spectral problems for star graphs of Stieltjes strings with Dirichlet and Neumann boundary conditions, respectively, at a selected vertex called root. The root is either the central vertex or, in the more challenging problem, a pendant vertex of the star graph. At all other pendant vertices Dirichlet conditions are imposed; at the central vertex, at which a mass may be placed, continuity and Kirchhoff conditions are assumed. We derive conditions on two sets of real numbers to be the spectra of the above Dirichlet and Neumann problems. Our solution for the inverse problems is constructive: we establish algorithms to recover the mass distribution on the star graph (i.e. the point masses and lengths of subintervals between them) from these two spectra and from the lengths of the separate strings. If the root is a pendant vertex, the two spectra uniquely determine the parameters on the main string (i.e. the string incident to the root) if the length of the main string is known. The mass distribution on the other edges need not be unique; the reason for this is the non-uniqueness caused by the non-strict interlacing of the given data in the case when the root is the central vertex. Finally, we relate of our results to tree-patterned matrix inverse problems.     

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.     

Divergence points of self-similar measures and packing dimension

Let μ be a self-similar measure in Rd. A point x∈Rd for which the limit does not exist is called a divergence point. Very recently there has been an enormous interest in investigating the fractal structure of various sets of divergence points. However, all previous work has focused exclusively on the study of the Hausdorff dimension of sets of divergence points and nothing is known about the packing dimension of sets of divergence points. In this paper we will give a systematic and detailed account of the problem of determining the packing dimensions of sets of divergence points of self-similar measures. An interesting and surprising consequence of our results is that, except for certain trivial cases, many natural sets of divergence points have distinct Hausdorff and packing dimensions.     

On the star-discrepancy of generalized Hammersley sequences in two dimensions

From a previous study in one dimension, precise estimates are deduced for the star discrepancy of some generalized Hammersley sequences in two dimensions, giving the lower constants presently known; also general bounds are obtained, and it is shown that these bounds are reached by the usual Hammersley sequences.     

On the Hausdorff dimension of fibres

It is well known that there are planar sets of Hausdorff dimension greater than 1 which are graphs of functions, i.e., all their vertical fibres consist of 1 point. We show this phenomenon does not occur for sets constructed in a certain “regular” fashion. Specifically, we consider sets obtained by partitioning a square into 4 subsquares, discarding 1 of them and repeating this on each of the 3 remaining squares, etc.; then almost all vertical fibres of a set so obtained have Hausdorff dimension at least 1/2. Sharp bounds on the dimensions of sets of exceptional fibres are presented. Partially supported by a grant from the Landau Centre for Mathematical Analysis.     

正实数维分形集的构造方法

给出了测量一类分形集维数的简单方法. 根据这种测量方法, 可以构造出任意实数维分形集,并且分形集可以不是自相似的.     

Ergodic properties for some non-expanding non-reversible systems

We study several properties of invariant measures obtained from preimages, for non-invertible maps on fractal sets which model non-reversible dynamical systems. We give two ways to describe the distribution of all preimages for endomorphisms which are not necessarily expanding on a basic set Λ. We give a topological dynamics condition which guarantees that the corresponding measures converge to a unique conformal ergodic borelian measure; this helps in estimating the unstable dimension a.e. with respect to this measure with the help of Lyapunov exponents. When there exist negative Lyapunov exponents of this limit measure, we study the conditional probabilities induced on the non-uniform local stable manifolds by the limit measure, and also its pointwise dimension on stable manifolds.     

On the negative case of the Singular Yamabe Problem

Let (M, g) be a compact Riemannian manifold of dimension n ≥3, and let Γ be a nonempty closed subset of M. The negative case of the Singular Yamabe Problem concerns the existence and behavior of a complete metric g on M∖Γ that has constant negative scalar curvature and is pointwise conformally related to the smooth metric g. Previous results have shown that when Γ is a smooth submanifold (with or without boundary) of dimension d, there exists such a metric if and only if . In this paper, we consider a more general class of closed sets and show the existence of a complete conformai metric ĝ with constant negative scalar curvature which depends on the dimension of the tangent cone to Γ at every point. Specifically, provided Γ admits a nice tangent cone at p, we show that when the dimension of the tangent cone to Γ at p is less than then there cannot exist a negative Singular Yamabe metric ĝ on M∖Γ.     

Weak tangent and level sets of Takagi functions

In this paper, we study some properties of Takagi functions and their level sets. We show that for Takagi functions $$T_{a,b}$$ with parameters a, b such that ab is a root of a Littlewood polynomial, there exist large level sets. As a consequence, we show that for some parameters a, b, the Assouad dimension of graphs of $$T_{a,b}$$ is strictly larger than their upper box dimension. In particular, we can find weak tangents of those graphs with large Hausdorff dimension, larger than the upper box dimension of the graphs.     

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.