Fast sampling method speeds up ferromagnetic Ising model computations
Near-linear-Time Sampling of the Ferromagnetic Ising Model at the Tree Uniqueness Threshold
Data Structures and Algorithms
Summary
The paper introduces a faster way to randomly sample configurations from a type of mathematical model used to study magnetic materials and other systems. The authors developed a method that works efficiently even at critical settings where older methods slow down. Their approach also applies to related models in physics, like the XY and Potts models. This lets people simulate these systems more quickly and accurately, which is useful for understanding complex behaviors in networks.
What this means in practice
- •For statistical physics simulators: Efficiently generate samples of ferromagnetic Ising and related models at critical thresholds to study magnetic phase transitions faster than traditional simulation methods.
- •For network analysts: Quickly sample configurations of network models similar to Ising and Potts for analyzing community structures and dependencies in large graphs.
Authors
Tianshun Miao
Abstract
We give a near-linear-time sampler for the zero-field ferromagnetic Ising model throughout the tree-uniqueness regime, including the threshold itself. The method also gives sampling algorithms for the XY and integer Potts models. On an $n$-vertex graph with $m$ edges and maximum degree at most $Δ$, we obtain the following expected-work bounds, with total variation error at most $\varepsilon$. 1.Near-linear Ising sampling. For $Δ\ge3$, the work is $O(n+m\log^3(n/\varepsilon))$ throughout the tree-uniqueness regime, including the threshold $β=Δ/(Δ-2)$. 2.Almost-linear XY sampling. For $Δ\ge8$, we sample the XY model in $\widetilde O(m+n^{1+o(1)})$ expected work at inverse-polynomial accuracy up to and including the robust phase-transition threshold on the $Δ$-regular tree. 3.Near-linear Potts sampling. For integer $q\ge3$, we sample the $q$-state Potts model in $\widetilde O(n+q^{O(1)}m)$ expected work whenever $β-1\le 0.1(β_{\mathrm{od}}(q,Δ)-1)$, where $β_{\mathrm{od}}$ is the ordered/disordered coexistence parameter. We express the even-subgraph representation of critical Ising as a polymer model that admits near-linear-time sampling, thereby bypassing the critical slowdown of Glauber and Swendsen--Wang dynamics. Building on the low-degree approximation approach of Miao and Yin, we establish general spectral conditions for fast polymer sampling. We verify these conditions through explorations that also implement the sampler efficiently, and apply the same framework to flow representations of the XY and Potts models. We also establish polynomial-time counting and sampling for the ferromagnetic XY model at every fixed temperature.