Cluster-Exact Approximation of Spin Glass Groundstates

Abstract

We present an algorithm which calculates groundstates of Ising spin glasses approximately. It works by randomly selecting clusters of spins which exhibit no frustrations. The spins which were not selected, contribute to the local fields of the selected spins. For the spin--cluster a groundstate is exactly calaculated by using graphtheoretical methods. The other spins remain unchanged. This procedure is repeated many times resulting in a state with low energy. The total time complexity of this scheme is approximately cubic. We estimate that the groundstate energy density of the infinite system for the +/- J model is -1.400 +/- 0.005 (2d) and -1.766 +/- 0.002 (3d). The distribution of overlaps for selected systems is calculated in order to characterize the algorithm.

13 pages, LaTeX (including figures in LaTeX-format)

References in corpus (3)

• A New Approach to Spin Glass Simulations
• Multicanonical Study of the 3D Ising Spin Glass
• A Rapid Dynamical Monte Carlo Algorithm for Glassy Systems

Cited by in corpus (20)

• Scaling of stiffness energy for 3d +/-J Ising spin glasses
• Finding Low-Temperature States with Parallel Tempering, Simulated Annealing and Simple Monte Carlo
• Hysteretic Optimization
• Ground-state behavior of the 3d +/-J random-bond Ising model
• Calculation of ground states of four-dimensional +or- J Ising spin glasses
• Ground-state clusters of two-, three- and four-dimensional +-J Ising spin glasses
• Evidence for existence of many pure ground states in 3d $\pm J$ Spin Glasses
• Spin Domains Generate Hierarchical Ground State Structure in J=+/-1 Spin Glasses
• The ground state energy of the Edwards-Anderson spin glass model with a parallel tempering Monte Carlo algorithm
• Dynamics of the Wang-Landau algorithm and complexity of rare events for the three-dimensional bimodal Ising spin glass
• Are Ground States of 3d +/-J Spin Glasses ultrametric ?
• A new method for analyzing ground-state landscapes: ballistic search
• Ground States and Defect Energies of the Two-dimensional XY Spin Glass from a Quasi-Exact Algorithm
• Genetic embedded matching approach to ground states in continuous-spin systems
• Ordered phase in the two-dimensional randomly coupled ferromagnet
• Direct sampling of complex landscapes at low temperatures: the three-dimensional +/-J Ising spin glass
• The dynamics of a driven harmonic oscillator coupled to independent Ising spins in random fields
• Dynamic Greedy Algorithms for the Edwards-Anderson Model
• Ferromagnetic-spin glass transition in four-dimensional random-bond Ising model
• Momentum-inspired Low-Rank Coordinate Descent for Diagonally Constrained SDPs