Weak convergence of Markov chain sampling methods and annealing algorithms to diffusions

Simulated annealing algorithms have traditionally been developed and analyzed along two distinct lines: Metropolis-type Markov chain algorithms and Langevin-type Markov diffusion algorithms. Here, we analyze the dynamics of continuous state Markov chains which arise from a particular implementation of the Metropolis and heat-bath Markov chain sampling methods. It is shown that certain continuous-time interpolations of the Metropolis and heat-bath chains converge weakly to Langevin diffusions running at different time scales. This exposes a close and potentially useful relationship between the Markov chain and diffusion versions of simulated annealing.The research reported here has been supported by the Whirlpool Foundation, by the Air Force Office of Scientific Research under Contract 89-0276, and by the Army Research Office under Contract DAAL-03-86-K-0171 (Center for Intelligent Control Systems).     

Factorizations of Polynomials over Noncommutative Algebras and Sufficient Sets of Edges in Directed Graphs

To directed graphs with unique sink and source we associate a noncommutative associative algebra and a polynomial over this algebra. Edges of the graph correspond to pseudo-roots of the polynomial. We give a sufficient condition when coefficients of the polynomial can be rationally expressed via elements of a given set of pseudo-roots (edges). Our results are based on a new theorem for directed graphs also proved in this paper. To the memory of Felix Alexandrovich Berezin. Vladimir Retakh was partially supported by NSA     

Coxeter matroid polytopes

If Δ is a polytope in real affine space, each edge of Δ determines a reflection in the perpendicular bisector of the edge. The exchange groupW (Δ) is the group generated by these reflections, and Δ is a (Coxeter) matroid polytope if this group is finite. This simple concept of matroid polytope turns out to be an equivalent way to define Coxeter matroids. The Gelfand-Serganova Theorem and the structure of the exchange group both give us information about the matroid polytope. We then specialize this information to the case of ordinary matroids; the matroid polytope by our definition in this case turns out to be a facet of the classical matroid polytope familiar to matroid theorists. This work was supported in part by NSA grant MDA904-95-1-1056.     

Helium and self-broadening in the first and second overtone bands of 12C16O

The pressure broadening coefficients for rotation-vibration lines of J states up to 22 in the 2-0 band and J states up to 20 in the 3-0 band of pure CO and HeCO mixtures were measured. The data were obtained at room temperature utilizing a Fourier transform spectrometer and various cells, including a 113-m White cell. These data exhibit little change with increasing vibrational level, and in the case of helium broadening, only slight J dependence.     

The spectral theory for a pencil of skewsymmetrical differential operators of the third order

We consider the linear algebra of a pair of skewsymmetrical forms in the space of periodic functions defined by differential operators. By linear transform in the space of functions we reduce this pair to the simplest possible form. In this process, we prove the theorem of reduction in rather general context. © 1994 John Wiley & Sons, Inc.