Mixing time and simulated annealing for the stochastic cellular automata

DOI10.1007/S10955-023-03090-XarXiv2007.11287MaRDI QIDQ6345606FDOQ6345606

Authors: Bruno Hideki Fukushima-Kimura, Satoshi Handa, Katsuhiro Kamakura, Yoshinori Kamijima, Kazushi Kawamura, Akira Sakai 

Publication date: 22 July 2020

Abstract: Finding a ground state of a given Hamiltonian of an Ising model on a graph $G=(V,E)$ 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 $log|V|$, and that (ii) if the temperature drops in time $n$ as $1/logn$, 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.

Mathematics Subject Classification ID

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)

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)