Mixing time and simulated annealing for the stochastic cellular automata
From MaRDI portal
Publication:6345606
Computational methods in Markov chains (60J22) Monte Carlo methods (65C05) Approximation methods and heuristics in mathematical programming (90C59) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Stochastic programming (90C15) Dynamical aspects of cellular automata (37B15) Cellular automata (computational aspects) (68Q80) Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics (82C20)
Abstract: Finding a ground state of a given Hamiltonian of an Ising model on a graph is an important but hard problem. The standard approach for this kind of problem is the application of algorithms that rely on single-spin-flip Markov chain Monte Carlo methods, such as the simulated annealing based on Glauber or Metropolis dynamics. In this paper, we investigate a particular kind of stochastic cellular automata, in which all spins are updated independently and simultaneously. We prove that (i) if the temperature is fixed sufficiently high, then the mixing time is at most of order , and that (ii) if the temperature drops in time as , then the limiting measure is uniformly distributed over the ground states. We also provide some simulations of the algorithms studied in this paper implemented on a GPU and show their superior performance compared to the conventional simulated annealing.
This page was built for publication: Mixing time and simulated annealing for the stochastic cellular automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6345606)
