TY - JOUR
T1 - Exact algorithm for sampling the two-dimensional Ising spin glass
AU - Thomas, Creighton K.
AU - Middleton, A. Alan
PY - 2009/10/30
Y1 - 2009/10/30
N2 - A sampling algorithm is presented that generates spin-glass configurations of the two-dimensional 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 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 (n3/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= 1282, with fixed and periodic boundary conditions.
AB - A sampling algorithm is presented that generates spin-glass configurations of the two-dimensional 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 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 (n3/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= 1282, with fixed and periodic boundary conditions.
UR - http://www.scopus.com/inward/record.url?scp=70449103059&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70449103059&partnerID=8YFLogxK
U2 - 10.1103/PhysRevE.80.046708
DO - 10.1103/PhysRevE.80.046708
M3 - Article
C2 - 19905483
AN - SCOPUS:70449103059
SN - 1063-651X
VL - 80
JO - Physical Review E - Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics
JF - Physical Review E - Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics
IS - 4
M1 - 046708
ER -