Misplaced Pages

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "KBD algorithm" – news · newspapers · books · scholar · JSTOR (May 2021) (Learn how and when to remove this message)

The KBD algorithm is a cluster update algorithm designed for the fully frustrated Ising model in two dimensions, or more generally any two dimensional spin glass with frustrated plaquettes arranged in a checkered pattern. It is discovered in 1990 by Daniel Kandel, Radel Ben-Av, and Eytan Domany, and generalized by P. D. Coddington and L. Han in 1994. It is the inspiration for cluster algorithms used in quantum monte carlo simulations.

Motivation

The SW algorithm is the first non-local algorithm designed for efficient simulation of ferromagnetic spin models. However, it is soon realized that the efficiency of the algorithm cannot be extended to frustrated systems, due to an overly large correlation length of the generated clusters with respect to the underlying spin system. The KBD algorithm is an attempt to extend the bond-formation rule to the plaquettes of the lattice, such that the generated clusters are informed by the frustration profile, resulting in them being smaller than the SW ones, thereby making the algorithm more efficient in comparison. However, at the current stage, it is not known whether this algorithm can be generalized for arbitrary spin glass models.

Algorithm

We begin by decomposing the square lattice down into plaquettes arranged in a checkered pattern (such that the plaquettes only overlap vertex-wise but not edge-wise). Since the spin model is fully-frustrated, each plaquette must contain exactly one or three negative interactions. If the plaquette contains three negative interactions, then no bonds can be formed. However, if the plaquette contains one negative interaction, then two parallel bonds can be formed (perpendicular to the negative edge) with probability ${\displaystyle p=1-e^{-4\beta }}$, where ${\displaystyle \beta }$ is the inverse temperature of the spin model.

The bonds will then form clusters on the lattice, on which the spins can be collectively flipped (either with the SW rule or the Wolff rule ). It can be shown that the update satisfies detailed balance, meaning that correctness is guaranteed if the algorithm is used in conjunction with ergodic algorithms like single spin-flip updates.

Topological features

At zero temperature, or the ${\displaystyle \beta \to \infty }$ limit, all the plaquettes will contain exactly one negative edge. In this case, on each checkered plaquette, the KBD algorithm will always open two parallel bonds perpendicular to the negative edge, meaning that the bond will be closed on the negative edge along with the edge opposite to it. If we were to track the closed bonds in the dual lattice, by drawing a straight/bent line inside each plaquette such that it intersects with the closed bonds, then it can be shown that a path following the lines must form a cycle.

Furthermore, it can be shown that there must be at least two such cycles, and that the cycles cannot intersect. Most importantly, each cycle cannot be contracted to a point in the underlying surface that the lattice is embedded in. On a periodic lattice (or a torus), this means that the cycles of closed bonds must wind around the torus in the same direction, from which one can show that the largest cluster (which must be "squeezed" between these cycles) at zero temperature cannot span a finite fraction of the lattice size in the thermodynamic limit.

References

1. ^ Kandel, Daniel; Ben-Av, Radel; Domany, Eytan (1990-08-20). "Cluster dynamics for fully frustrated systems". Physical Review Letters. 65 (8): 941–944. Bibcode:1990PhRvL..65..941K. doi:10.1103/PhysRevLett.65.941. PMID 10043065.
2. Hamze, Firas; Jacob, Darryl C.; Ochoa, Andrew J.; Perera, Dilina; Wang, Wenlong; Katzgraber, Helmut G. (2018-04-13). "From near to eternity: Spin-glass planting, tiling puzzles, and constraint-satisfaction problems". Physical Review E. 97 (4): 043303. arXiv:1711.04083. Bibcode:2018PhRvE..97d3303H. doi:10.1103/PhysRevE.97.043303. PMID 29758754.
3. ^ Coddington, P. D.; Han, L. (1994-08-01). "Generalized cluster algorithms for frustrated spin models". Physical Review B. 50 (5): 3058–3067. arXiv:cond-mat/9402030. Bibcode:1994PhRvB..50.3058C. doi:10.1103/PhysRevB.50.3058. PMID 9976551. S2CID 939709.
4. Swendsen, Robert H.; Wang, Jian-Sheng (1987-01-12). "Nonuniversal critical dynamics in Monte Carlo simulations". Physical Review Letters. 58 (2): 86–88. Bibcode:1987PhRvL..58...86S. doi:10.1103/PhysRevLett.58.86. PMID 10034599.
5. Cataudella, V. (1992-05-01). "Percolation transition in systems with frustation". Physica A: Statistical Mechanics and Its Applications. 183 (3): 249–254. Bibcode:1992PhyA..183..249C. doi:10.1016/0378-4371(92)90145-G. ISSN 0378-4371.
6. Kandel, Daniel; Ben-Av, Radel; Domany, Eytan (1992-03-01). "Cluster Monte Carlo dynamics for the fully frustrated Ising model". Physical Review B. 45 (9): 4700–4709. Bibcode:1992PhRvB..45.4700K. doi:10.1103/PhysRevB.45.4700. PMID 10002105.

v t e Statistical mechanics
Theory	Principle of maximum entropy ergodic theory
Statistical thermodynamics	Ensembles partition functions equations of state thermodynamic potential: U H F G Maxwell relations
Models	Ferromagnetism models Ising Potts Heisenberg percolation Particles with force field depletion force Lennard-Jones potential
Mathematical approaches	Boltzmann equation H-theorem Vlasov equation BBGKY hierarchy stochastic process mean-field theory and conformal field theory
Critical phenomena	Phase transition Critical exponents correlation length size scaling
Entropy	Boltzmann Shannon Tsallis Rényi von Neumann
Applications	Statistical field theory elementary particle superfluidity Condensed matter physics Complex system chaos information theory Boltzmann machine

• Statistical mechanics
• Monte Carlo methods