Multilevel hybrid split-step implicit tau-leap

In biochemically reactive systems with small copy numbers of one or more reactant molecules, the dynamics is dominated by stochastic effects. To approximate those systems, discrete state-space and stochastic simulation approaches have been shown to be more relevant than continuous state-space and deterministic ones. In systems characterized by having simultaneously fast and slow timescales, existing discrete space-state stochastic path simulation methods, such as the stochastic simulation algorithm (SSA) and the explicit tau-leap (explicit-TL) method, can be very slow. Implicit approximations have been developed to improve numerical stability and provide efficient simulation algorithms for those systems. Here, we propose an efficient Multilevel Monte Carlo (MLMC) method in the spirit of the work by Anderson and Higham (SIAM Multiscal Model. Simul. 10(1), 2012). This method uses split-step implicit tau-leap (SSI-TL) at levels where the explicit-TL method is not applicable due to numerical stability issues. We present numerical examples that illustrate the performance of the proposed method.     

Inversion of Chernoff’s theorem

In this paper, we prove a theorem which is the inversion of Chernoff’s theorem. As a consequence of this result, we obtain conditions for the validity of the Chernoff and Trotter product formulas.     

Chernoff bounds for mean overflow rates

A number of independent traffic streams arrive at a queueing node which provides a finite buffer and a non-idling service at constant rate. Customers which arrive when the buffer is full are dropped and counted as overflows. We present Chernoff type bounds for mean overflow rates in the form of finite-dimensional minimization problems. The results are based on bounds for moment generating functions of buffer and bandwidth usage of the individual streams in an infinite buffer with constant service rate. We calculate these functions for regulated, Poisson and certain on/off sources. The achievable statistical multiplexing gain and the tightness of the bounds are demonstrated by several numerical examples.     

New method for constructing Chernoff functions

We state and, for the first time, prove a theorem in the theory of strongly continuous operator semigroups. This theorem, which has essentially been suggested by O.G. Smolyanov, in particular, enables one to reduce solving the Schr¨odinger equation to solving the heat equation.     

Chernoff’s theorem on one-parametric semigroups

A closability of operators appearing under some analytic conditions close to conditions of the well-known Chernoff theorem on approximation of one-parametric operator semigroups is proved, existence of a semigroup is not required. An example of a nonclosed operator satisfying these conditions is presented.     

Chernoff approximations of Feller semigroups in Riemannian manifolds

Chernoff approximations of Feller semigroups and the associated diffusion processes in Riemannian manifolds are studied. The manifolds are assumed to be of bounded geometry, thus including all compact manifolds and also a wide range of non-compact manifolds. Sufficient conditions are established for a class of second order elliptic operators to generate a Feller semigroup on a (generally non-compact) manifold of bounded geometry. A construction of Chernoff approximations is presented for these Feller semigroups in terms of shift operators. This provides approximations of solutions to initial value problems for parabolic equations with variable coefficients on the manifold. It also yields weak convergence of a sequence of random walks on the manifolds to the diffusion processes associated with the elliptic generator. For parallelizable manifolds this result is applied in particular to the representation of Brownian motion on the manifolds as limits of the corresponding random walks.     

Chernoff bounds for discriminating between two markov processes

We study a statistical hypothesis testing problem, where a sample function of a Markov process with one of two sets of known parameters is observed over a finite time interval. When a log likelihood ratio test is used to discriminate between the two sets of parameters, we give bounds on the probability of choosing an incorrect hypothesis, and on the total probability of error, for both discrete and continuous time parameter, and discrete and continuous state space. The asymptotic behavior of the bounds is examined as the observation interval becomes infinite.     

A remark to the preceding paper by Chernoff

It is shown that the method of Chernoff developed in the preceding paper can be modified to prove the essential self-adjointness on C₀^∞(R^m) of all positive powers of the Schrödinger operator T = ? Δ + q if q real and in C^∞(R^m) and if $\text{T ? ?a ? b ¦ x ¦}{}^2\text{on}\text{C}{}_0{}^{\mathrm{\infty }}\text{(R}{}^{\mathrm{m}}\text{)}$.     

Stabilizations of the Trotter-Kato theorem and the Chernoff product formula

This paper concerns versions of the Trotter-Kato Theorem and the Chernoff Product Formula for C ₀-semigroups in the absence of stability. Applications to ${\mathcal{A}}$ -stable rational approximations of semigroups are presented.     

Local Chernoff and Hodges-Lehmann efficiencies of linear rank tests for symmetry

One computes the local asymptotic Chernoff and Hodges—Lehmann efficiencies of linear rank statistics for the testing of symmetry under certain regularity conditions, imposed on the labels and on the distribution of the observations under the alternative. It is revealed that these efficiencies coincide with the previously known Pitman and local Bahadur efficiencies.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova Akademii Nauk SSSR, Vol. 184, pp. 215–226, 1990.     

Multilevel preconditioning

Summary This paper is concerned with multilevel techniques for preconditioning linear systems arising from Galerkin methods for elliptic boundary value problems. A general estimate is derived which is based on the characterization of Besov spaces in terms of weighted sequence norms related to corresponding multilevel expansions. The result brings out clearly how the various ingredients of a typical multilevel setting affect the growth rate of the condition numbers. In particular, our analysis indicates how to realize even uniformly bounded condition numbers. For example, the general results are used to show that the Bramble-Pasciak-Xu preconditioner for piecewise linear finite elements gives rise to uniformly bounded condition numbers even when the refinements of the underlying triangulations are highly nonuniform. Furthermore, they are applied to a general multivariate setting of refinable shift-invariant spaces, in particular, covering those induced by various types of wavelets.The work of this author was partially supported by the Air Force Office of Scientific Research (Contract No. 89/0455) and by the Office of Naval Research (Contract No. N00014/90/1343) during her stay at the Department of Mathematics, University of South Carolina, Columbia, SC 29208, USA.     

Speed of Convergence of Chernoff Approximations to Solutions of Evolution Equations

Mathematical Notes -     

Rate of Convergence of Chernoff Approximations of Operator $$C_0$$ -Semigroups

Mathematical Notes -     

Multilevel Schwarz methods

Summary We consider the solution of the algebraic system of equations which result from the discretization of second order elliptic equations. A class of multilevel algorithms are studied using the additive Schwarz framework. We establish that the condition number of the iteration operators are bounded independent of mesh sizes and the number of levels. This is an improvement on Dryja and Widlund's result on a multilevel additive Schwarz algorithm, as well as Bramble, Pasciak and Xu's result on the BPX algorithm. Some multiplicative variants of the multilevel methods are also considered. We establish that the energy norms of the corresponding iteration operators are bounded by a constant less than one, which is independent of the number of levels. For a proper ordering, the iteration operators correspond to the error propagation operators of certain V-cycle multigrid methods, using Gauss-Seidel and damped Jacobi methods as smoothers, respectively.This work was supported in part by the National Science Foundation under Grants NSF-CCR-8903003 at Courant Institute of Mathematical Sciences, New York University and NSF-ASC-8958544 at Department of Computer Science, University of Maryland.     

Multilevel ILU decomposition

Summary. In this paper, the multilevel ILU (MLILU) decomposition is introduced. During an incomplete Gaussian elimination process new matrix entries are generated such that a special ordering strategy yields distinct levels. On these levels, some smoothing steps are computed. The MLILU decomposition exists and the corresponding iterative scheme converges for all symmetric and positive definite matrices. Convergence rates independent of the number of unknowns are shown numerically for several examples. Many numerical experiments including unsymmetric and anisotropic problems, problems with jumping coefficients as well as realistic problems are presented. They indicate a very robust convergence behavior of the MLILU method. Received June 13, 1997 / Revised version received March 17, 1998     

Chernoff efficiency of the sign and Wilcoxon tests for testing the symmetry hypothesis

The local Chernoff efficiency of the sign and Wilcoxon statistics are derived for the testing of symmetry on the basis of the analysis of the probabilities of large deviations of these statistics under the hypothesis and the alternative.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova Akademii Nauk SSSR, Vol. 177, pp. 101–107, 1989.     

Topographical Multilevel Single Linkage

An iterative topographical Multilevel Single Linkage (TMSL) method has been introduced. The approach uses topographical information on the objective function, in particular theg-nearest-neighbour graph. The algorithm uses evenly distributed points from a Halten sequence of uniform limiting density. We discuss the implementation of the algorithm and compare its performance with other well-known algorithms. The new algorithm performs much better (in some cases several times) than the Multilevel Single Linkage method in terms of number of function evaluations but is not quite so competitive with respect to CPU time.     

Majorations de Chernoff pour des chaînes de Markov contrÔlées

Résumé Let but de cet article est d'établir des majorations de Chernoff pour des chaÎnes de Markov contrÔlées, semblables à celles de Donsker et Varadhan [1] pour les chaÎnes non contrÔlées. On applique les résultats obtenus à un problème de gain optimal en moyenne sous contraintes.Dans un article ultérieur, on exposera une application à des problèmes de tests séquentiels.