A construction of polynomial lattice rules with small gain coefficients

In this paper we construct polynomial lattice rules which have, in some sense, small gain coefficients using a component-by-component approach. The gain coefficients, as introduced by Owen, indicate to what degree the method improves upon Monte Carlo. We show that the variance of an estimator based on a scrambled polynomial lattice rule constructed component-by-component decays at a rate of N ^{−(2α+1)+δ} , for all δ > 0, assuming that the function under consideration has bounded variation of order α for some 0 < α ≤ 1, and where N denotes the number of quadrature points. An analogous result is obtained for Korobov polynomial lattice rules. It is also established that these rules are almost optimal for the function space considered in this paper. Furthermore, we discuss the implementation of the component-by-component approach and show how to reduce the computational cost associated with it. Finally, we present numerical results comparing scrambled polynomial lattice rules and scrambled digital nets.     

Parameter-robust numerical method for a system of singularly perturbed initial value problems

In this work we study a system of M( ≥ 2) first-order singularly perturbed ordinary differential equations with given initial conditions. The leading term of each equation is multiplied by a distinct small positive parameter, which induces overlapping layers. A maximum principle does not, in general, hold for this system. It is discretized using backward Euler difference scheme for which a general convergence result is derived that allows to establish nodal convergence of O(N ^− 1ln N) on the Shishkin mesh and O(N ^− 1) on the Bakhvalov mesh, where N is the number of mesh intervals and the convergence is robust in all of the parameters. Numerical experiments are performed to support the theoretical results.     

Spectral estimates for Schrödinger operators with sparse potentials on graphs

A construction of “sparse potentials,” suggested by the authors for the lattice \mathbbZ^d {\mathbb{Z}^d} , d > 2, is extended to a large class of combinatorial and metric graphs whose global dimension is a number D > 2. For the Schr?dinger operator − Δ − αV on such graphs, with a sparse potential V, we study the behavior (as α → ∞) of the number N_(−Δ − αV) of negative eigenvalues of − Δ − αV. We show that by means of sparse potentials one can realize any prescribed asymptotic behavior of N_(−Δ − αV) under very mild regularity assumptions. A similar construction works also for the lattice \mathbbZ² {\mathbb{Z}^2} , where D = 2. Bibliography: 13 titles.     

Piecewise-linear,discontinuous Galerkin method for a fractional diffusion equation

We use a piecewise-linear, discontinuous Galerkin method for the time discretization of a fractional diffusion equation involving a parameter in the range − 1 < α < 0. Our analysis shows that, for a time interval (0,T) and a spatial domain Ω, the error in L_￥((0,T);L₂(W))L_\infty\bigr((0,T);L_2(\Omega)\bigr) is of order k ^2 + α , where k denotes the maximum time step. Since derivatives of the solution may be singular at t = 0, our result requires the use of non-uniform time steps. In the limiting case α = 0 we recover the known O(k ²) convergence for the classical diffusion (heat) equation. We also consider a fully-discrete scheme that employs standard (continuous) piecewise-linear finite elements in space, and show that the additional error is of order h ²log(1/k). Numerical experiments indicate that our O(k ^2 + α ) error bound is pessimistic. In practice, we observe O(k ²) convergence even for α close to − 1.     

On the local convergence of a family of Euler-Halley type iterations with a parameter

This paper aims to study the local convergence of a family of Euler-Halley type methods with a parameter α for solving nonlinear operator equations under the second-order generalized Lipschitz assumption. The radius r _α of the optimal convergence ball and the error estimation of the method corresponding to α are estimated for each α ∈ ( − ∞ , + ∞ ). For each α > 0, we get r _α  ≥ r _− α and the upper bound of the error estimation of the method with α > 0 is not larger than the one with α < 0. For each α ≤ 0, we get the precise value of r _α , which is closely linked to the dynamical property of the method applied to a real or a complex function, and the optimal error estimation, which decreases when α→0⁻. Results show that the method corresponding to α is better than the one corresponding to − α for each α > 0 and the Chebyshev-Euler method is the best among all methods in the family with α ∈ ( − ∞ , 0] from the view of both safe choice of the initial point and error estimation.     

Transversal fluctuations for increasing subsequences on the plane

Consider a realization of a Poisson process in ℝ² with intensity 1 and take a maximal up/right path from the origin to (N, N) consisting of line segments between the points, where maximal means that it contains as many points as possible. The number of points in such a path has fluctuations of order N ^χ, where χ = 1/3, [BDJ]. Here we show that typical deviations of a maximal path from the diagonal x = y is of order N ^ξ with ξ = 2/3. This is consistent with the scaling identity χ = 2ξ− 1 which is believed to hold in many random growth models. Received: 16 April 1999 / Revised version: 5 July 1999 / Published online: 14 February 2000     

Alternative dual frames for digital-to-analog conversion in sigma–delta quantization

We design alternative dual frames for linearly reconstructing signals from sigma–delta (ΣΔ) quantized finite frame coefficients. In the setting of sampling expansions for bandlimited functions, it is known that a stable rth order sigma–delta quantizer produces approximations where the approximation error is at most of order 1 / λ ^r , and λ > 1 is the oversampling ratio. We show that the counterpart of this result is not true for several families of redundant finite frames for \mathbbR^d\mathbb{R}^d when the canonical dual frame is used in linear reconstruction. As a remedy, we construct alternative dual frame sequences which enable an rth order sigma–delta quantizer to achieve approximation error of order 1/N ^r for certain sequences of frames where N is the frame size. We also present several numerical examples regarding the constructions.     

Spreading-invariant sequences and processes on bounded index sets

We say that a random sequence is spreadable if all subsequences of equal length have the same distribution. For infinite sequences the notion is equivalent to exchangeability but for finite sequences it is more general. The present paper is devoted to a systematic study of finite spreadable sequences and of processes on [0, 1] with spreadable increments. In particular, we show how many basic results in the exchangeable case—notably the predictable sampling theorem, the Wald-type identities, and various martingale and weak convergence results—admit extensions to a spreadable setting. We also identify some additional conditions that ensure the exchangeability of a spreadable sequence or process. Received: 9 November 1999 / Revised version: 16 March 2000 / Published online: 18 September 2000     

Random Partial Orders Defined by Angular Domains

The d-dimensional random partial order is the intersection of d independently and uniformly chosen (with replacement) linear orders on the set [n] = {1, 2, . . . , n}. This is equivalent to picking n points uniformly at random in the d-dimensional unit cube Q_d=[0,1]^dQ_d=[0,1]^d with the coordinate-wise ordering. If d = 2, then this can be rephrased by declaring that for any pair P ₁, P ₂ ∈ Q ₂ we have P ₁ ≺ P ₂ if and only if P ₂ lies in the positive upper quadrant defined by the two axis-parallel lines crossing at P ₁. In this paper we study the random partial order with parameter α (0 ≤ α ≤ π) which is generated by picking n points uniformly at random from Q ₂ equipped with the same partial order as above but with the quadrant replaced by an angular domain of angle α.     

The Schwartz Space and Homogeneous Distributions on H-Type Groups

 Let N be an H-type group of homogeneous dimension Q. We study the space of biradial Schwartz functions on N by means of the Gelfand transform. This enables us to characterize the class of biradial homogeneous distributions on N of degree α, with 0 ? α< Q, which are away from the identity, via the Gelfand transform. (Received 26 April 2000; in revised form December 2000)     

Quasi-<Emphasis Type="Italic">L</Emphasis><Superscript><Emphasis Type="Italic">p</Emphasis></Superscript> norm orthogonal Galerkin expansions in sums of Jacobi polynomials

In the study of differential equations on [ − 1,1] subject to linear homogeneous boundary conditions of finite order, it is often expedient to represent the solution in a Galerkin expansion, that is, as a sum of basis functions, each of which satisfies the given boundary conditions. In order that the functions be maximally distinct, one can use the Gram-Schmidt method to generate a set orthogonal with respect to a particular weight function. Here we consider all such sets associated with the Jacobi weight function, w(x) = (1 − x) ^α (1 + x) ^β . However, this procedure is not only cumbersome for sets of large degree, but does not provide any intrinsic means to characterize the functions that result. We show here that each basis function can be written as the sum of a small number of Jacobi polynomials, whose coefficients are found by imposing the boundary conditions and orthogonality to the first few basis functions only. That orthogonality of the entire set follows—a property we term “auto-orthogonality”—is remarkable. Additionally, these basis functions are shown to behave asymptotically like individual Jacobi polynomials and share many of the latter’s useful properties. Of particular note is that these basis sets retain the exponential convergence characteristic of Jacobi expansions for expansion of an arbitrary function satisfying the boundary conditions imposed. Further, the associated error is asymptotically minimized in an L ^p(α) norm given the appropriate choice of α = β. The rich algebraic structure underlying these properties remains partially obscured by the rather difficult form of the non-standard weighted integrals of Jacobi polynomials upon which our analysis rests. Nevertheless, we are able to prove most of these results in specific cases and certain of the results in the general case. However a proof that such expansions can satisfy linear boundary conditions of arbitrary order and form appears extremely difficult.     

Gauss-Hermite quadratures for functions from Hilbert spaces with Gaussian reproducing kernels

We study univariate integration with the Gaussian weight for a positive variance α. This is done for the reproducing kernel Hilbert space with the Gaussian kernel for a positive shape parameter γ. We study Gauss-Hermite quadratures, although this choice of quadratures may be questionable since polynomials do not belong to this space of functions. Nevertheless, we provide the explicit formula for the error of the Gauss-Hermite quadrature using n function values. In particular, for 2αγ ²<1 we have an exponential rate of convergence, and for 2αγ ²=1 we have no convergence, whereas for 2αγ ²>1 we have an exponential divergence.     

Global Heat Kernel Estimates for Relativistic Stable Processes in Half-space-like Open Sets

In this paper, by using probabilistic methods, we establish sharp two-sided large time estimates for the transition densities of relativistic α-stable processes with mass m ∈ (0, 1] (i.e., for the Dirichlet heat kernels of m − (m ^2/α  − Δ) ^α/2 with m ∈ (0, 1]) in half-space-like C ^{1, 1} open sets. The estimates are uniform in m in the sense that the constants are independent of m ∈ (0, 1]. Combining with the sharp two-sided small time estimates, established in Chen et al. (Ann Probab, 2011), valid for all C ^{1, 1} open sets, we have now sharp two-sided estimates for the transition densities of relativistic α-stable processes with mass m ∈ (0, 1] in half-space-like C ^{1, 1} open sets for all times. Integrating the heat kernel estimates with respect to the time variable, one can recover the sharp two-sided Green function estimates for relativistic α-stable processes with mass m ∈ (0, 1] in half-space-like C ^{1, 1} open sets established recently in Chen et al. (Stoch Process their Appl, 2011).     

O(dlog?N)-Quantics Approximation of N-d Tensors in High-Dimensional Numerical Modeling

In the present paper, we discuss the novel concept of super-compressed tensor-structured data formats in high-dimensional applications. We describe the multifolding or quantics-based tensor approximation method of O(dlog N)-complexity (logarithmic scaling in the volume size), applied to the discrete functions over the product index set {1,…,N}^⊗d , or briefly N-d tensors of size N ^d , and to the respective discretized differential-integral operators in ℝ ^d . As the basic approximation result, we prove that a complex exponential sampled on an equispaced grid has quantics rank 1. Moreover, a Chebyshev polynomial, sampled over a Chebyshev Gauss–Lobatto grid, has separation rank 2 in the quantics tensor format, while for the polynomial of degree m over a Chebyshev grid the respective quantics rank is at most 2m+1. For N-d tensors generated by certain analytic functions, we give a constructive proof of the O(dlog Nlog ε ⁻¹)-complexity bound for their approximation by low-rank 2-(dlog N) quantics tensors up to the accuracy ε>0. In the case ε=O(N ^−α ), α>0, our approach leads to the quantics tensor numerical method in dimension d, with the nearly optimal asymptotic complexity O(d/αlog ² ε ⁻¹). From numerical examples presented here, we observe that the quantics tensor method has proved its value in application to various function related tensors/matrices arising in computational quantum chemistry and in the traditional finite element method/boundary element method (FEM/BEM). The tool apparently works.     

On Borell-Brascamp-Lieb Inequalities on Metric Measure Spaces

In this paper we introduce the notion of a Borell-Brascamp-Lieb inequality for metric measure spaces (M,d,m) denoted by BBL(K,N) for two numbers K,N ∈ ℝ with N ≥ 1. In the first part we prove that BBL(K,N) holds true on metric measure spaces satisfying a curvature-dimension condition CD(K,N) developed and studied by Lott and Villani in (Ann Math 169:903–991, 2007) as well as by Sturm in (Acta Math 196(1):133–177, 2006). The aim of the second part is to show that BBL(K,N) is stable under convergence of metric measure spaces with respect to the L ₂-transportation distance.     

Ray Hölder-continuity for fractional Sobolev spaces in infinite dimensions and applications

We prove H?lder-continuity on rays in the direction of vectors in the (generalized) Cameron-Martin space for functions in Sobolev spaces in L ^p of fractional order α∈ (, 1) over infinite dimensional linear spaces. The underlying measures are required to satisfy some easy standard structural assumptions only. Apart from Wiener measure they include Gibbs measures on a lattice and Euclidean interacting quantum fields in infinite volume. A number of applications, e.g., to the two-dimensional polymer measure, are presented. In particular, irreducibility of the Dirichlet form associated with the latter measure is proved without restrictions on the coupling constant. Received: 9 November 1998 / Published online: 30 March 2000     

A particle approximation of the solution of the Kushner–Stratonovitch equation

We construct a sequence of branching particle systems α _n convergent in measure to the solution of the Kushner–Stratonovitch equation. The algorithm based on this result can be used to solve numerically the filtering problem. We prove that the rate of convergence of the algorithm is of order n ^?. This paper is the third in a sequence, and represents the most efficient algorithm we have identified so far. Received: 4 February 1997 / Revised version: 26 October 1998     

Automatic grid control in adaptive BVP solvers

Grid adaptation in two-point boundary value problems is usually based on mapping a uniform auxiliary grid to the desired nonuniform grid. Here we combine this approach with a new control system for constructing a grid density function ϕ(x). The local mesh width Δx _j + 1/2 = x _j + 1 − x _j with 0 = x ₀ < x ₁ < ... < x _N  = 1 is computed as Δx _j + 1/2 = ε _N / φ _j + 1/2, where {j_j+1/2}₀^N-1\{\varphi_{j+1/2}\}_0^{N-1} is a discrete approximation to the continuous density function ϕ(x), representing mesh width variation. The parameter ε _N  = 1/N controls accuracy via the choice of N. For any given grid, a solver provides an error estimate. Taking this as its input, the feedback control law then adjusts the grid, and the interaction continues until the error has been equidistributed. Digital filters may be employed to process the error estimate as well as the density to ensure the regularity of the grid. Once ϕ(x) is determined, another control law determines N based on the prescribed tolerance TOL{\textsc {tol}}. The paper focuses on the interaction between control system and solver, and the controller’s ability to produce a near-optimal grid in a stable manner as well as correctly predict how many grid points are needed. Numerical tests demonstrate the advantages of the new control system within the bvpsuite solver, ceteris paribus, for a selection of problems and over a wide range of tolerances. The control system is modular and can be adapted to other solvers and error criteria.     

Carleson type estimates for second order elliptic equations with unbounded drift

We derive a Carleson type estimate for positive solutions of non-divergence second order elliptic equations Lu = a _ij D _ij u + b _i D _i u = 0 in a bounded domain Ω ⊂ ℝ ⁿ . We assume that b _i ∈ L ⁿ (Ω) and Ω is a twisted H?lder domain of order α ∈ (1/2, 1] which satisfies a weak regularity condition. We also provide an example which shows that the main result fails in general if α ∈ (0, 1/2]. Bibliography: 18 titles.