Performance Limitations of Flat Histogram Methods and Optimality of Wang-Landau Sampling
arXiv:cond-mat/0306108 · doi:10.1103/PhysRevLett.92.097201
Abstract
We determine the optimal scaling of local-update flat-histogram methods with system size by using a perfect flat-histogram scheme based on the exact density of states of 2D Ising models.The typical tunneling time needed to sample the entire bandwidth does not scale with the number of spins N as the minimal N^2 of an unbiased random walk in energy space. While the scaling is power law for the ferromagnetic and fully frustrated Ising model, for the +/- J nearest-neighbor spin glass the distribution of tunneling times is governed by a fat-tailed Frechet extremal value distribution that obeys exponential scaling. We find that the Wang-Landau algorithm shows the same scaling as the perfect scheme and is thus optimal.
arXiv comment5 pages, 6 figures
References in corpus (18)
- 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
- On the Wang-Landau Method for Off-Lattice Simulations in the "Uniform" Ensemble
- Transition Matrix Monte Carlo Method
- Density of States Monte Carlo Method for Simulation of Fluids
- An improved Monte Carlo method for direct calculation of the density of states
- Transition Matrix Monte Carlo Reweighting and Dynamics
- Wang-Landau sampling for quantum systems: algorithms to overcome tunneling problems and calculate the free energy
- Sampling along reaction coordinates with the Wang-Landau method
- Potential of Mean Force between a Spherical Particle Suspended in a Nematic Liquid Crystal and a Substrate
- Three-dimensional antiferromagnetic q-state Potts models: application of the Wang-Landau algorithm
- Flat Histogram Method of Wang-Landau and N-fold Way
- Combination of improved multibondic method and the Wang-Landau method
- Multicanonical Spin Glass Simulations
- A new approach to the study of the ground-state properties of 2D Ising spin glass
Cited by in corpus (58)
- Continuous-time Monte Carlo methods for quantum impurity models
- Feedback-optimized parallel tempering Monte Carlo
- Optimized parallel tempering simulations of proteins
- Fast Algorithm to Calculate Density of States
- Understanding and Improving the Wang-Landau Algorithm
- Optimizing the ensemble for equilibration in broad-histogram Monte Carlo simulations
- Wang-Landau algorithm for continuous models and joint density of states
- Wang-Landau Algorithm: a Theoretical Analysis of the Saturation of the Error
- Generalized Ensemble and Tempering Simulations: A Unified View
- Convergence and Refinement of the Wang-Landau Algorithm
- Density of States for a Specified Correlation Function and the Energy Landscape
- Optimal Modification Factor and Convergence of the Wang-Landau Algorithm
- Football fever: goal distributions and non-Gaussian statistics
- Entropic sampling via Wang-Landau random walks in dominant energy subspaces
- First-order transition features of the 3D bimodal random-field Ising model
- Heavy tails in the distribution of time-to-solution for classical and quantum annealing
- Parallel multicanonical study of the three-dimensional Blume-Capel model
- Wang-Landau sampling: Improving accuracy
- Sampling motif-constrained ensembles of networks
- Quenched bond randomness in marginal and non-marginal Ising spin models in 2D
- Dynamics of the Wang-Landau algorithm and complexity of rare events for the three-dimensional bimodal Ising spin glass
- Optimized ensemble Monte Carlo simulations of dense Lennard-Jones fluids
- Overcoming the critical slowing down of flat-histogram Monte Carlo simulations: Cluster updates and optimized broad-histogram ensembles
- Universality aspects of the 2d random-bond Ising and 3d Blume-Capel models
- First-order transition features of the triangular Ising model with nearest- and next-nearest-neighbor antiferromagnetic interactions
- Performance of Wang-Landau algorithm in continuous spin models and a case study : modified XY-model
- Lower bounds for Ramsey numbers as a statistical physics problem
- Fast Flat-Histogram Method for Generalized Spin Models
- Manifold Learning in Atomistic Simulations: A Conceptual Review
- Optimized multicanonical simulations: a new proposal based on classical fluctuation theory
- On the non-convergence of the Wang-Landau algorithms with multiple random walkers
- Optimized Broad-Histogram Ensembles for the Simulation of Quantum Systems
- Monte Carlo Sampling in Fractal Landscapes
- Genetic embedded matching approach to ground states in continuous-spin systems
- Optimized broad-histogram simulations for strong first-order phase transitions: Droplet transitions in the large-Q Potts model
- Multicanonical Sampling of the Space of States of H(2,n)-Vector Models
- Efficiency of Monte Carlo Sampling in Chaotic Systems
- Static critical behavior of the states Potts model: High-resolution entropic study
- Universal features and tail analysis of the order-parameter distribution of the two-dimensional Ising model: An entropic sampling Monte Carlo study
- Elementary excitations and the phase transition in the bimodal Ising spin glass model
- A new Wang-Landau approach to obtain phase diagrams for multicomponent alloys
- Analytical study of tunneling times in flat histogram Monte Carlo
- Importance Sampling of Rare Events in Chaotic Systems
- Intrinsic convergence properties of entropic sampling algorithms
- The Wang-Landau Algorithm as Stochastic Optimization and Its Acceleration
- Energy gap of the bimodal two-dimensional Ising spin glass
- On properties of the Wang--Landau algorithm
- Perturbation method to calculate the density of states
- Extended canonical Monte Carlo methods: Improving accuracy of microcanonical calculations using a re-weighting technique
- Applying the Wang-Landau Algorithm to Lattice Gauge Theory
- Typical versus average helicity modulus in the three-dimensional gauge glass: Understanding the vortex glass phase
- Performance of Wang-Landau algorithm in lattice model of liquid crystals
- Avoiding critical slowdown in models with SALR interactions
- Stochastic Approximation Monte Carlo with a Dynamic Update Factor
- On the mixing time in the Wang-Landau algorithm
- Quantum Annealing Algorithms for Estimating Ising Partition Functions
- Projected single-spin flip dynamics in the Ising Model
- On the nature of the phase transitions in two-dimensional type II superconductors