Exact Algorithm for Sampling the 2D Ising Spin Glass

Abstract

A sampling algorithm is presented that generates spin glass configurations of the 2D Edwards-Anderson Ising spin glass at finite temperature, with probabilities proportional to their Boltzmann weights. Such an algorithm overcomes the slow dynamics of direct simulation and can be used to study long-range correlation functions and coarse-grained dynamics. The algorithm uses a correspondence between spin configurations on a regular lattice and dimer (edge) coverings of a related graph: Wilson's algorithm [D. B. Wilson, Proc. 8th Symp. Discrete Algorithms 258, (1997)] for sampling dimer coverings on a planar lattice is adapted to generate samplings for the dimer problem corresponding to both planar and toroidal spin glass samples. This algorithm is recursive: it computes probabilities for spins along a "separator" that divides the sample in half. Given the spins on the separator, sample configurations for the two separated halves are generated by further division and assignment. The algorithm is simplified by using Pfaffian elimination, rather than Gaussian elimination, for sampling dimer configurations. For n spins and given floating point precision, the algorithm has an asymptotic run-time of O(n^{3/2}); it is found that the required precision scales as inverse temperature and grows only slowly with system size. Sample applications and benchmarking results are presented for samples of size up to n=128^2, with fixed and periodic boundary conditions.

18 pages, 10 figures, 1 table; minor clarifications

References in corpus (27)

• Optimization with Extremal Dynamics
• Universality in three-dimensional Ising spin glasses: A Monte Carlo study
• Nature of the Spin Glass State
• A Cluster Monte Carlo Algorithm for 2-Dimensional Spin Glasses
• Absence of an Almeida-Thouless line in Three-Dimensional Spin Glasses
• Pfaffian pairing and backflow wave functions for electronic structure quantum Monte Carlo methods
• The critical exponents of the two-dimensional Ising spin glass revisited: Exact Ground State Calculations and Monte Carlo Simulations
• Nonequilibrium spin glass dynamics from picoseconds to 0.1 seconds
• Domain growth morphology in curvature driven two dimensional coarsening
• Strong universality and algebraic scaling in two-dimensional Ising spin glasses
• Renormalization for Discrete Optimization
• Domain-Wall Energies and Magnetization of the Two-Dimensional Random-Bond Ising Model
• Large-Scale, Low-Energy Excitations in the Two-Dimensional Ising Spin Glass
• Correlation length of the two-dimensional Ising spin glass with bimodal interactions
• Critical thermodynamics of the two-dimensional +/-J Ising spin glass
• Matching Kasteleyn Cities for Spin Glass Ground States
• Aging, rejuvenation and memory phenomena in spin glasses
• Fractal dimension of domain walls in two-dimensional Ising spin glasses
• "Exact" Algorithm for Random-Bond Ising Models in 2D
• Effective critical behavior of the two-dimensional Ising spin glass with bimodal interactions
• Temperature Chaos, Rejuvenation and Memory in Migdal-Kadanoff Spin Glasses
• Thermodynamics of Mesoscopic Vortex Systems in 1+1 Dimensions
• Evidence for universal scaling in the spin-glass phase
• Growing length scales during aging in 2d disordered systems
• A Worm Algorithm for Two-Dimensional Spin Glasses
• Renormalization group approach to exact sampling
• Persistence and Memory in Patchwork Dynamics for Glassy Models

Cited by in corpus (24)

• Efficient numerical computation of the Pfaffian for dense and banded skew-symmetric matrices
• Zero and low temperature behavior of the two-dimensional $\pm J$ Ising spin glass
• Chaos and universality in two-dimensional Ising spin glasses
• Simplest model to study reentrance in physical systems
• Domain-wall excitations in the two-dimensional Ising spin glass
• Numeric and symbolic evaluation of the pfaffian of general skew-symmetric matrices
• Technical aspects of the evaluation of the overlap of Hartree- Fock- Bogoliubov wave functions
• Which measures of spin-glass overlaps are informative?
• Ground-state topology of the Edwards-Anderson +/-J spin glass model
• Replica Cluster Variational Method: the Replica Symmetric solution for the 2D random bond Ising model
• Characterizing and Improving Generalized Belief Propagation Algorithms on the 2D Edwards-Anderson Model
• Universality in phase boundary slopes for spin glasses on self dual lattices
• A very fast inference algorithm for finite-dimensional spin glasses: Belief Propagation on the dual lattice
• Numerically exact correlations and sampling in the two-dimensional Ising spin glass
• Optimizing glassy p-spin models
• Elementary excitations and the phase transition in the bimodal Ising spin glass model
• A factorization algorithm to compute Pfaffians
• Sampling the ground-state magnetization of d-dimensional p-body Ising models
• Tractable Minor-free Generalization of Planar Zero-field Ising Models
• Loop-corrected belief propagation for lattice spin models
• A New Family of Tractable Ising Models
• On one-step replica symmetry breaking in the Edwards-Anderson spin glass model
• Determination of electron-hole correlation length in CdSe quantum dots using explicitly correlated two-particle cumulant
• Damage spreading and coupling in spin glasses and hard spheres