Exact Ground States of Large Two-Dimensional Planar Ising Spin Glasses

Pardella, Gregor and Liers, Frauke (2008) Exact Ground States of Large Two-Dimensional Planar Ising Spin Glasses.
Published in: Physical Review E Vol. 78 (5). 056705.


We present an algorithm for the calculation of exact ground states of two-dimensional Ising spin glasses with free boundary conditions in at least one direction. Studying spin-glass physics through analyzing their ground-state properties has a long history. Although there exist polynomial-time algorithms for the two-dimensional planar case, where the problem of finding ground states is transformed to a minimum weighted perfect matching problem, the reachable system sizes have been limited both by the needed CPU time and memory requirements. Using Kasteleyn cities, we calculate accurate ground states for huge two-dimensional planar Ising spin-glass lattices (up to 3000x3000 spins) within reasonable time. According to our knowledge, these are the largest sizes currently available. Kasteleyn cities were recently also used by Thomas and Middleton in the context of extended ground states on the torus. Domain walls can be computed using reoptimization. Finally, the correctness of heuristically computed ground states can easily be verified.

Download: [img] Postscript - Preprinted Version
Download (612kB) | Preview
Download: [img] PDF - Preprinted Version
Download (245kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2008-569
Depositing User: Gregor Pardella
Date Deposited: 29 Jan 2009 00:00
Last Modified: 19 Dec 2011 09:44
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/569