Dynamics of the Wang-Landau algorithm and complexity of rare events for the three-dimensional bimodal Ising spin glass
arXiv:cond-mat/0405409 · doi:10.1088/1742-5468/2004/07/P07008
Abstract
We investigate the performance of flat-histogram methods based on a multicanonical ensemble and the Wang-Landau algorithm for the three-dimensional +/- J spin glass by measuring round-trip times in the energy range between the zero-temperature ground state and the state of highest energy. Strong sample-to-sample variations are found for fixed system size and the distribution of round-trip times follows a fat-tailed Frechet extremal value distribution. Rare events in the fat tails of these distributions corresponding to extremely slowly equilibrating spin glass realizations dominate the calculations of statistical averages. While the typical round-trip time scales exponential as expected for this NP-hard problem, we find that the average round-trip time is no longer well-defined for systems with N >= 8^3 spins. We relate the round-trip times for multicanonical sampling to intrinsic properties of the energy landscape and compare with the numerical effort needed by the genetic Cluster-Exact Approximation to calculate the exact ground state energies. For systems with N >= 8^3 spins the simulation of these rare events becomes increasingly hard. For N >= 14^3 there are samples where the Wang-Landau algorithm fails to find the true ground state within reasonable simulation times. We expect similar behavior for other algorithms based on multicanonical sampling.
arXiv comment9 pages, 12 figures
References in corpus (13)
- An efficient, multiple range random walk algorithm to calculate the density of states
- Exchange Monte Carlo Method and Application to Spin Glass Simulations
- Simulated Tempering: A New Monte Carlo Scheme
- Multicanonical Ensemble: A New Approach to Simulate First-order Phase Transitions
- Determining the density of states for classical statistical models: A random walk algorithm to produce a flat histogram
- Critical Behavior of the Three-Dimensional Ising Spin Glass
- Scaling corrections: site-percolation and Ising model in three dimensions
- Transition Matrix Monte Carlo Method
- Universal Finite Size Scaling Functions in the 3D Ising Spin Glass
- Transition Matrix Monte Carlo Reweighting and Dynamics
- Performance Limitations of Flat Histogram Methods and Optimality of Wang-Landau Sampling
- Scaling of stiffness energy for 3d +/-J Ising spin glasses
- Cluster-Exact Approximation of Spin Glass Groundstates
Cited by in corpus (17)
- Feedback-optimized parallel tempering Monte Carlo
- A generic, hierarchical framework for massively parallel Wang-Landau sampling
- Heavy tails in the distribution of time-to-solution for classical and quantum annealing
- The ground state energy of the Edwards-Anderson spin glass model with a parallel tempering Monte Carlo algorithm
- Quenched bond randomness in marginal and non-marginal Ising spin models in 2D
- Correlations between the dynamics of parallel tempering and the free-energy landscape in spin glasses
- Analysis and Optimization of Population Annealing
- A new paradigm for petascale Monte Carlo simulation: Replica exchange Wang-Landau sampling
- Wang-Landau study of the critical behaviour of the bimodal 3D-Random Field Ising Model
- Multicanonical entropy like-solution of statistical temperature weighted histogram analysis method (ST-WHAM)
- Universality aspects of the 2d random-bond Ising and 3d Blume-Capel models
- Exploring new frontiers in statistical physics with a new, parallel Wang-Landau framework
- Optimized broad-histogram simulations for strong first-order phase transitions: Droplet transitions in the large-Q Potts model
- A portable and flexible implementation of the Wang--Landau algorithm in order to determine the Density of States
- Magnetic phase transition in coupled spin-lattice systems: A replica-exchange Wang-Landau study
- The Wang-Landau Algorithm as Stochastic Optimization and Its Acceleration
- Nonflat Histogram Techniques for Spin Glasses