Dresden 2017 – scientific programme
Parts | Days | Selection | Search | Updates | Downloads | Help
DY: Fachverband Dynamik und Statistische Physik
DY 11: Critical phenomena
DY 11.9: Talk
Monday, March 20, 2017, 17:45–18:00, HÜL 186
Approximate ground states of the random-field Potts model from graph cuts and parallel tempering — Manoj Kumar1, •Ravinder Kumar2,3, Varsha Banerjee4, Sanjay Puri1, Martin Weigel2, and Wolfhard Janke3 — 1School of Physical Sciences, Jawaharlal Nehru University,New Delhi-110067, India — 2Applied Mathematics Research Centre, Coventry University, Coventry, UK. — 3Institut für Theoretische Physik, Leipzig University, Leipzig, Germany. — 4Department of Physics, Indian Institute of Technology, Hauz Khas, New Delhi - 110016, India.
While the ground-state problem for the random-field Ising model is polynomial, and can be
solved using a number of well known algorithms for maximum flow, the analogue
random-field Potts model corresponds to a multi-terminal flow problem that is known
to be NP hard. Hence an efficient exact algorithm is extremely unlikely to exist. Still,
it is possible to employ embedding of binary degrees of freedom into the Potts spins to use
graph-cut methods to solve the corresponding ground-state problem approximately with
polynomial methods. It is shown here that this works relatively well. We compare results
produced by this heuristic algorithm to energy minima found by an appropriately tuned
parallel tempering method that is configured to find ground states for the considered
system sizes with high probability. The method based on graph cuts finds the same states
in a fraction of the time. The new method is used for a first exploratory study of the
random-field Potts model in two dimensions.