KBD algorithm - Revision history

OAbot: Open access bot: url-access updated in citation with #oabot.

2025-05-26T20:00:53Z

Open access bot: url-access updated in citation with #oabot.

← Previous revision		Revision as of 20:00, 26 May 2025
Line 2:		Line 2:
	{{refimprove\|date=May 2021}}		{{refimprove\|date=May 2021}}

	The '''KBD algorithm''' is a [[Swendsen–Wang algorithm\|cluster update algorithm]] designed for the [[Domino tiling\|fully frustrated Ising model]] in two dimensions,<ref name=":0">{{Cite journal\|last1=Kandel\|first1=Daniel\|last2=Ben-Av\|first2=Radel\|last3=Domany\|first3=Eytan\|date=1990-08-20\|title=Cluster dynamics for fully frustrated systems\|url=https://link.aps.org/doi/10.1103/PhysRevLett.65.941\|journal=Physical Review Letters\|volume=65\|issue=8\|pages=941–944\|doi=10.1103/PhysRevLett.65.941\|pmid=10043065\|bibcode=1990PhRvL..65..941K}}</ref> or more generally any two dimensional spin glass with frustrated plaquettes arranged in a [[Check (pattern)\|checkered pattern]].<ref>{{Cite journal\|last1=Hamze\|first1=Firas\|last2=Jacob\|first2=Darryl C.\|last3=Ochoa\|first3=Andrew J.\|last4=Perera\|first4=Dilina\|last5=Wang\|first5=Wenlong\|last6=Katzgraber\|first6=Helmut G.\|date=2018-04-13\|title=From near to eternity: Spin-glass planting, tiling puzzles, and constraint-satisfaction problems\|journal=Physical Review E\|volume=97\|issue=4\|pages=043303\|doi=10.1103/PhysRevE.97.043303\|pmid=29758754\|arxiv=1711.04083\|bibcode=2018PhRvE..97d3303H\|doi-access=free}}</ref> 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.<ref name=coddington>{{Cite journal\|last1=Coddington\|first1=P. D.\|last2=Han\|first2=L.\|date=1994-08-01\|title=Generalized cluster algorithms for frustrated spin models\|url=https://link.aps.org/doi/10.1103/PhysRevB.50.3058\|journal=Physical Review B\|volume=50\|issue=5\|pages=3058–3067\|doi=10.1103/PhysRevB.50.3058\|pmid=9976551\|arxiv=cond-mat/9402030\|bibcode=1994PhRvB..50.3058C\|s2cid=939709}}</ref> It is the inspiration for cluster algorithms used in [[Quantum Monte Carlo\|quantum monte carlo]] simulations.		The '''KBD algorithm''' is a [[Swendsen–Wang algorithm\|cluster update algorithm]] designed for the [[Domino tiling\|fully frustrated Ising model]] in two dimensions,<ref name=":0">{{Cite journal\|last1=Kandel\|first1=Daniel\|last2=Ben-Av\|first2=Radel\|last3=Domany\|first3=Eytan\|date=1990-08-20\|title=Cluster dynamics for fully frustrated systems\|url=https://link.aps.org/doi/10.1103/PhysRevLett.65.941\|journal=Physical Review Letters\|volume=65\|issue=8\|pages=941–944\|doi=10.1103/PhysRevLett.65.941\|pmid=10043065\|bibcode=1990PhRvL..65..941K\|url-access=subscription}}</ref> or more generally any two dimensional spin glass with frustrated plaquettes arranged in a [[Check (pattern)\|checkered pattern]].<ref>{{Cite journal\|last1=Hamze\|first1=Firas\|last2=Jacob\|first2=Darryl C.\|last3=Ochoa\|first3=Andrew J.\|last4=Perera\|first4=Dilina\|last5=Wang\|first5=Wenlong\|last6=Katzgraber\|first6=Helmut G.\|date=2018-04-13\|title=From near to eternity: Spin-glass planting, tiling puzzles, and constraint-satisfaction problems\|journal=Physical Review E\|volume=97\|issue=4\|pages=043303\|doi=10.1103/PhysRevE.97.043303\|pmid=29758754\|arxiv=1711.04083\|bibcode=2018PhRvE..97d3303H\|doi-access=free}}</ref> 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.<ref name=coddington>{{Cite journal\|last1=Coddington\|first1=P. D.\|last2=Han\|first2=L.\|date=1994-08-01\|title=Generalized cluster algorithms for frustrated spin models\|url=https://link.aps.org/doi/10.1103/PhysRevB.50.3058\|journal=Physical Review B\|volume=50\|issue=5\|pages=3058–3067\|doi=10.1103/PhysRevB.50.3058\|pmid=9976551\|arxiv=cond-mat/9402030\|bibcode=1994PhRvB..50.3058C\|s2cid=939709}}</ref> It is the inspiration for cluster algorithms used in [[Quantum Monte Carlo\|quantum monte carlo]] simulations.

	== Motivation ==		== Motivation ==
	The [[Swendsen–Wang algorithm\|SW algorithm]] is the first non-local algorithm designed for efficient simulation of [[Ising model\|ferromagnetic spin models]].<ref>{{Cite journal\|last1=Swendsen\|first1=Robert H.\|last2=Wang\|first2=Jian-Sheng\|date=1987-01-12\|title=Nonuniversal critical dynamics in Monte Carlo simulations\|url=https://link.aps.org/doi/10.1103/PhysRevLett.58.86\|journal=Physical Review Letters\|volume=58\|issue=2\|pages=86–88\|doi=10.1103/PhysRevLett.58.86\|pmid=10034599\|bibcode=1987PhRvL..58...86S}}</ref> However, it is soon realized that the efficiency of the algorithm cannot be extended to [[Geometrical frustration\|frustrated systems]], due to an overly large [[Percolation critical exponents\|correlation length of the generated clusters]] with respect to the underlying spin system.<ref>{{Cite journal\|last=Cataudella\|first=V.\|date=1992-05-01\|title=Percolation transition in systems with frustation\|url=https://dx.doi.org/10.1016/0378-4371%2892%2990145-G\|journal=Physica A: Statistical Mechanics and Its Applications\|language=en\|volume=183\|issue=3\|pages=249–254\|doi=10.1016/0378-4371(92)90145-G\|bibcode=1992PhyA..183..249C\|issn=0378-4371}}</ref> 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,<ref name=coddington/> 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.		The [[Swendsen–Wang algorithm\|SW algorithm]] is the first non-local algorithm designed for efficient simulation of [[Ising model\|ferromagnetic spin models]].<ref>{{Cite journal\|last1=Swendsen\|first1=Robert H.\|last2=Wang\|first2=Jian-Sheng\|date=1987-01-12\|title=Nonuniversal critical dynamics in Monte Carlo simulations\|url=https://link.aps.org/doi/10.1103/PhysRevLett.58.86\|journal=Physical Review Letters\|volume=58\|issue=2\|pages=86–88\|doi=10.1103/PhysRevLett.58.86\|pmid=10034599\|bibcode=1987PhRvL..58...86S\|url-access=subscription}}</ref> However, it is soon realized that the efficiency of the algorithm cannot be extended to [[Geometrical frustration\|frustrated systems]], due to an overly large [[Percolation critical exponents\|correlation length of the generated clusters]] with respect to the underlying spin system.<ref>{{Cite journal\|last=Cataudella\|first=V.\|date=1992-05-01\|title=Percolation transition in systems with frustation\|url=https://dx.doi.org/10.1016/0378-4371%2892%2990145-G\|journal=Physica A: Statistical Mechanics and Its Applications\|language=en\|volume=183\|issue=3\|pages=249–254\|doi=10.1016/0378-4371(92)90145-G\|bibcode=1992PhyA..183..249C\|issn=0378-4371\|url-access=subscription}}</ref> 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,<ref name=coddington/> 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 ==		== Algorithm ==
Line 15:		Line 15:
	At zero temperature, or the <math>\beta \to \infty</math> limit, all the plaquettes will contain exactly one negative edge. In this case, on each checkered plaquette, the KBD algorithm will always [[Percolation theory\|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 (graph theory)\|cycle]].		At zero temperature, or the <math>\beta \to \infty</math> limit, all the plaquettes will contain exactly one negative edge. In this case, on each checkered plaquette, the KBD algorithm will always [[Percolation theory\|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 (graph theory)\|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 [[Homotopy\|contracted]] to a point in the [[Euler characteristic\|underlying surface]] that the lattice is [[Graph embedding\|embedded]] in.<ref>{{Cite journal\|last1=Kandel\|first1=Daniel\|last2=Ben-Av\|first2=Radel\|last3=Domany\|first3=Eytan\|date=1992-03-01\|title=Cluster Monte Carlo dynamics for the fully frustrated Ising model\|url=https://link.aps.org/doi/10.1103/PhysRevB.45.4700\|journal=Physical Review B\|volume=45\|issue=9\|pages=4700–4709\|doi=10.1103/PhysRevB.45.4700\|pmid=10002105\|bibcode=1992PhRvB..45.4700K}}</ref> 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 [[Giant component\|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]].		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 [[Homotopy\|contracted]] to a point in the [[Euler characteristic\|underlying surface]] that the lattice is [[Graph embedding\|embedded]] in.<ref>{{Cite journal\|last1=Kandel\|first1=Daniel\|last2=Ben-Av\|first2=Radel\|last3=Domany\|first3=Eytan\|date=1992-03-01\|title=Cluster Monte Carlo dynamics for the fully frustrated Ising model\|url=https://link.aps.org/doi/10.1103/PhysRevB.45.4700\|journal=Physical Review B\|volume=45\|issue=9\|pages=4700–4709\|doi=10.1103/PhysRevB.45.4700\|pmid=10002105\|bibcode=1992PhRvB..45.4700K\|url-access=subscription}}</ref> 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 [[Giant component\|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 ==		== References ==

Pol098 at 17:40, 11 January 2022

2022-01-11T17:40:36Z

← Previous revision		Revision as of 17:40, 11 January 2022
Line 2:		Line 2:
	{{refimprove\|date=May 2021}}		{{refimprove\|date=May 2021}}

	The '''KBD algorithm''' is a [[Swendsen–Wang algorithm\|cluster update algorithm]] designed for the [[Domino tiling\|fully frustrated Ising model]] in two dimensions,<ref name=":0">{{Cite journal\|last1=Kandel\|first1=Daniel\|last2=Ben-Av\|first2=Radel\|last3=Domany\|first3=Eytan\|date=1990-08-20\|title=Cluster dynamics for fully frustrated systems\|url=https://link.aps.org/doi/10.1103/PhysRevLett.65.941\|journal=Physical Review Letters\|volume=65\|issue=8\|pages=941–944\|doi=10.1103/PhysRevLett.65.941\|pmid=10043065\|bibcode=1990PhRvL..65..941K}}</ref> or more generally any two dimensional spin glass with frustrated plaquettes arranged in a [[Check (pattern)\|checkered pattern]].<ref>{{Cite journal\|last1=Hamze\|first1=Firas\|last2=Jacob\|first2=Darryl C.\|last3=Ochoa\|first3=Andrew J.\|last4=Perera\|first4=Dilina\|last5=Wang\|first5=Wenlong\|last6=Katzgraber\|first6=Helmut G.\|date=2018-04-13\|title=From near to eternity: Spin-glass planting, tiling puzzles, and constraint-satisfaction problems\|journal=Physical Review E\|volume=97\|issue=4\|pages=043303\|doi=10.1103/PhysRevE.97.043303\|pmid=29758754\|arxiv=1711.04083\|bibcode=2018PhRvE..97d3303H\|doi-access=free}}</ref> 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.<ref>{{Cite journal\|last1=Coddington\|first1=P. D.\|last2=Han\|first2=L.\|date=1994-08-01\|title=Generalized cluster algorithms for frustrated spin models\|url=https://link.aps.org/doi/10.1103/PhysRevB.50.3058\|journal=Physical Review B\|volume=50\|issue=5\|pages=3058–3067\|doi=10.1103/PhysRevB.50.3058\|pmid=9976551\|arxiv=cond-mat/9402030\|bibcode=1994PhRvB..50.3058C\|s2cid=939709}}</ref> It is the inspiration for cluster algorithms used in [[Quantum Monte Carlo\|quantum monte carlo]] simulations.		The '''KBD algorithm''' is a [[Swendsen–Wang algorithm\|cluster update algorithm]] designed for the [[Domino tiling\|fully frustrated Ising model]] in two dimensions,<ref name=":0">{{Cite journal\|last1=Kandel\|first1=Daniel\|last2=Ben-Av\|first2=Radel\|last3=Domany\|first3=Eytan\|date=1990-08-20\|title=Cluster dynamics for fully frustrated systems\|url=https://link.aps.org/doi/10.1103/PhysRevLett.65.941\|journal=Physical Review Letters\|volume=65\|issue=8\|pages=941–944\|doi=10.1103/PhysRevLett.65.941\|pmid=10043065\|bibcode=1990PhRvL..65..941K}}</ref> or more generally any two dimensional spin glass with frustrated plaquettes arranged in a [[Check (pattern)\|checkered pattern]].<ref>{{Cite journal\|last1=Hamze\|first1=Firas\|last2=Jacob\|first2=Darryl C.\|last3=Ochoa\|first3=Andrew J.\|last4=Perera\|first4=Dilina\|last5=Wang\|first5=Wenlong\|last6=Katzgraber\|first6=Helmut G.\|date=2018-04-13\|title=From near to eternity: Spin-glass planting, tiling puzzles, and constraint-satisfaction problems\|journal=Physical Review E\|volume=97\|issue=4\|pages=043303\|doi=10.1103/PhysRevE.97.043303\|pmid=29758754\|arxiv=1711.04083\|bibcode=2018PhRvE..97d3303H\|doi-access=free}}</ref> 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.<ref name=coddington>{{Cite journal\|last1=Coddington\|first1=P. D.\|last2=Han\|first2=L.\|date=1994-08-01\|title=Generalized cluster algorithms for frustrated spin models\|url=https://link.aps.org/doi/10.1103/PhysRevB.50.3058\|journal=Physical Review B\|volume=50\|issue=5\|pages=3058–3067\|doi=10.1103/PhysRevB.50.3058\|pmid=9976551\|arxiv=cond-mat/9402030\|bibcode=1994PhRvB..50.3058C\|s2cid=939709}}</ref> It is the inspiration for cluster algorithms used in [[Quantum Monte Carlo\|quantum monte carlo]] simulations.

	== Motivation ==		== Motivation ==
	The [[Swendsen–Wang algorithm\|SW algorithm]] is the first non-local algorithm designed for efficient simulation of [[Ising model\|ferromagnetic spin models]].<ref>{{Cite journal\|last1=Swendsen\|first1=Robert H.\|last2=Wang\|first2=Jian-Sheng\|date=1987-01-12\|title=Nonuniversal critical dynamics in Monte Carlo simulations\|url=https://link.aps.org/doi/10.1103/PhysRevLett.58.86\|journal=Physical Review Letters\|volume=58\|issue=2\|pages=86–88\|doi=10.1103/PhysRevLett.58.86\|pmid=10034599\|bibcode=1987PhRvL..58...86S}}</ref> However, it is soon realized that the efficiency of the algorithm cannot be extended to [[Geometrical frustration\|frustrated systems]], due to an overly large [[Percolation critical exponents\|correlation length of the generated clusters]] with respect to the underlying spin system.<ref>{{Cite journal\|last=Cataudella\|first=V.\|date=1992-05-01\|title=Percolation transition in systems with frustation\|url=https://dx.doi.org/10.1016/0378-4371%2892%2990145-G\|journal=Physica A: Statistical Mechanics and Its Applications\|language=en\|volume=183\|issue=3\|pages=249–254\|doi=10.1016/0378-4371(92)90145-G\|bibcode=1992PhyA..183..249C\|issn=0378-4371}}</ref> 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,<ref~~>{{Cite~~ ~~journal\|last1~~=Coddington\|first1=P. D.\|last2=Han\|first2=L.\|date=1994-08-01\|title=Generalized cluster algorithms for frustrated spin models\|url=https://link.aps.org/doi/10.1103/PhysRevB.50.3058\|journal=Physical Review B\|volume=50\|issue=5\|pages=3058–3067\|doi=10.1103/PhysRevB.50.3058\|pmid=9976551\|arxiv=cond-mat/9402030\|bibcode=1994PhRvB..50.3058C\|s2cid=939709}}</~~ref~~> 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.		The [[Swendsen–Wang algorithm\|SW algorithm]] is the first non-local algorithm designed for efficient simulation of [[Ising model\|ferromagnetic spin models]].<ref>{{Cite journal\|last1=Swendsen\|first1=Robert H.\|last2=Wang\|first2=Jian-Sheng\|date=1987-01-12\|title=Nonuniversal critical dynamics in Monte Carlo simulations\|url=https://link.aps.org/doi/10.1103/PhysRevLett.58.86\|journal=Physical Review Letters\|volume=58\|issue=2\|pages=86–88\|doi=10.1103/PhysRevLett.58.86\|pmid=10034599\|bibcode=1987PhRvL..58...86S}}</ref> However, it is soon realized that the efficiency of the algorithm cannot be extended to [[Geometrical frustration\|frustrated systems]], due to an overly large [[Percolation critical exponents\|correlation length of the generated clusters]] with respect to the underlying spin system.<ref>{{Cite journal\|last=Cataudella\|first=V.\|date=1992-05-01\|title=Percolation transition in systems with frustation\|url=https://dx.doi.org/10.1016/0378-4371%2892%2990145-G\|journal=Physica A: Statistical Mechanics and Its Applications\|language=en\|volume=183\|issue=3\|pages=249–254\|doi=10.1016/0378-4371(92)90145-G\|bibcode=1992PhyA..183..249C\|issn=0378-4371}}</ref> 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,<ref name=coddington/> 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 ==		== Algorithm ==

Citation bot: Alter: url, journal. URLs might have been anonymized. Add: s2cid, arxiv, bibcode, pmid, authors 1-1. Removed proxy/dead URL that duplicated identifier. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Abductive | Category:Statistical mechanics | #UCB_Category 24/278

2021-10-21T15:05:27Z

Alter: url, journal. URLs might have been anonymized. Add: s2cid, arxiv, bibcode, pmid, authors 1-1. Removed proxy/dead URL that duplicated identifier. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Abductive | Category:Statistical mechanics | #UCB_Category 24/278

← Previous revision		Revision as of 15:05, 21 October 2021
Line 2:		Line 2:
	{{refimprove\|date=May 2021}}		{{refimprove\|date=May 2021}}

	The '''KBD algorithm''' is a [[Swendsen–Wang algorithm\|cluster update algorithm]] designed for the [[Domino tiling\|fully frustrated Ising model]] in two dimensions,<ref name=":0">{{Cite journal\|~~last~~=Kandel\|~~first~~=Daniel\|last2=Ben-Av\|first2=Radel\|last3=Domany\|first3=Eytan\|date=1990-08-20\|title=Cluster dynamics for fully frustrated systems\|url=https://link.aps.org/doi/10.1103/PhysRevLett.65.941\|journal=Physical Review Letters\|volume=65\|issue=8\|pages=941–944\|doi=10.1103/PhysRevLett.65.941}}</ref> or more generally any two dimensional spin glass with frustrated plaquettes arranged in a [[Check (pattern)\|checkered pattern]].<ref>{{Cite journal\|~~last~~=Hamze\|~~first~~=Firas\|last2=Jacob\|first2=Darryl C.\|last3=Ochoa\|first3=Andrew J.\|last4=Perera\|first4=Dilina\|last5=Wang\|first5=Wenlong\|last6=Katzgraber\|first6=Helmut G.\|date=2018-04-13\|title=From near to eternity: Spin-glass planting, tiling puzzles, and constraint-satisfaction problems~~\|url=https://link.aps.org/doi/10.1103/PhysRevE.97.043303~~\|journal=Physical Review E\|volume=97\|issue=4\|pages=043303\|doi=10.1103/PhysRevE.97.043303\|doi-access=free}}</ref> 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.<ref>{{Cite journal\|~~last~~=Coddington\|~~first~~=P. D.\|last2=Han\|first2=L.\|date=1994-08-01\|title=Generalized cluster algorithms for frustrated spin models\|url=https://link.aps.org/doi/10.1103/PhysRevB.50.3058\|journal=Physical Review B\|volume=50\|issue=5\|pages=3058–3067\|doi=10.1103/PhysRevB.50.3058\|arxiv=cond-mat/9402030}}</ref> It is the inspiration for cluster algorithms used in [[Quantum Monte Carlo\|quantum monte carlo]] simulations.		The '''KBD algorithm''' is a [[Swendsen–Wang algorithm\|cluster update algorithm]] designed for the [[Domino tiling\|fully frustrated Ising model]] in two dimensions,<ref name=":0">{{Cite journal\|last1=Kandel\|first1=Daniel\|last2=Ben-Av\|first2=Radel\|last3=Domany\|first3=Eytan\|date=1990-08-20\|title=Cluster dynamics for fully frustrated systems\|url=https://link.aps.org/doi/10.1103/PhysRevLett.65.941\|journal=Physical Review Letters\|volume=65\|issue=8\|pages=941–944\|doi=10.1103/PhysRevLett.65.941\|pmid=10043065\|bibcode=1990PhRvL..65..941K}}</ref> or more generally any two dimensional spin glass with frustrated plaquettes arranged in a [[Check (pattern)\|checkered pattern]].<ref>{{Cite journal\|last1=Hamze\|first1=Firas\|last2=Jacob\|first2=Darryl C.\|last3=Ochoa\|first3=Andrew J.\|last4=Perera\|first4=Dilina\|last5=Wang\|first5=Wenlong\|last6=Katzgraber\|first6=Helmut G.\|date=2018-04-13\|title=From near to eternity: Spin-glass planting, tiling puzzles, and constraint-satisfaction problems\|journal=Physical Review E\|volume=97\|issue=4\|pages=043303\|doi=10.1103/PhysRevE.97.043303\|pmid=29758754\|arxiv=1711.04083\|bibcode=2018PhRvE..97d3303H\|doi-access=free}}</ref> 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.<ref>{{Cite journal\|last1=Coddington\|first1=P. D.\|last2=Han\|first2=L.\|date=1994-08-01\|title=Generalized cluster algorithms for frustrated spin models\|url=https://link.aps.org/doi/10.1103/PhysRevB.50.3058\|journal=Physical Review B\|volume=50\|issue=5\|pages=3058–3067\|doi=10.1103/PhysRevB.50.3058\|pmid=9976551\|arxiv=cond-mat/9402030\|bibcode=1994PhRvB..50.3058C\|s2cid=939709}}</ref> It is the inspiration for cluster algorithms used in [[Quantum Monte Carlo\|quantum monte carlo]] simulations.

	== Motivation ==		== Motivation ==
	The [[Swendsen–Wang algorithm\|SW algorithm]] is the first non-local algorithm designed for efficient simulation of [[Ising model\|ferromagnetic spin models]].<ref>{{Cite journal\|~~last~~=Swendsen\|~~first~~=Robert H.\|last2=Wang\|first2=Jian-Sheng\|date=1987-01-12\|title=Nonuniversal critical dynamics in Monte Carlo simulations\|url=https://link.aps.org/doi/10.1103/PhysRevLett.58.86\|journal=Physical Review Letters\|volume=58\|issue=2\|pages=86–88\|doi=10.1103/PhysRevLett.58.86}}</ref> However, it is soon realized that the efficiency of the algorithm cannot be extended to [[Geometrical frustration\|frustrated systems]], due to an overly large [[Percolation critical exponents\|correlation length of the generated clusters]] with respect to the underlying spin system.<ref>{{Cite journal\|last=Cataudella\|first=V.\|date=1992-05-01\|title=Percolation transition in systems with frustation\|url=https://~~www~~.~~sciencedirect~~.~~com~~/~~science~~/~~article/pii/037843719290145G~~\|journal=Physica A: Statistical Mechanics and ~~its~~ Applications\|language=en\|volume=183\|issue=3\|pages=249–254\|doi=10.1016/0378-4371(92)90145-G\|issn=0378-4371}}</ref> 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,<ref>{{Cite journal\|~~last~~=Coddington\|~~first~~=P. D.\|last2=Han\|first2=L.\|date=1994-08-01\|title=Generalized cluster algorithms for frustrated spin models\|url=https://link.aps.org/doi/10.1103/PhysRevB.50.3058\|journal=Physical Review B\|volume=50\|issue=5\|pages=3058–3067\|doi=10.1103/PhysRevB.50.3058\|arxiv=cond-mat/9402030}}</ref> 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.		The [[Swendsen–Wang algorithm\|SW algorithm]] is the first non-local algorithm designed for efficient simulation of [[Ising model\|ferromagnetic spin models]].<ref>{{Cite journal\|last1=Swendsen\|first1=Robert H.\|last2=Wang\|first2=Jian-Sheng\|date=1987-01-12\|title=Nonuniversal critical dynamics in Monte Carlo simulations\|url=https://link.aps.org/doi/10.1103/PhysRevLett.58.86\|journal=Physical Review Letters\|volume=58\|issue=2\|pages=86–88\|doi=10.1103/PhysRevLett.58.86\|pmid=10034599\|bibcode=1987PhRvL..58...86S}}</ref> However, it is soon realized that the efficiency of the algorithm cannot be extended to [[Geometrical frustration\|frustrated systems]], due to an overly large [[Percolation critical exponents\|correlation length of the generated clusters]] with respect to the underlying spin system.<ref>{{Cite journal\|last=Cataudella\|first=V.\|date=1992-05-01\|title=Percolation transition in systems with frustation\|url=https://dx.doi.org/10.1016/0378-4371%2892%2990145-G\|journal=Physica A: Statistical Mechanics and Its Applications\|language=en\|volume=183\|issue=3\|pages=249–254\|doi=10.1016/0378-4371(92)90145-G\|bibcode=1992PhyA..183..249C\|issn=0378-4371}}</ref> 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,<ref>{{Cite journal\|last1=Coddington\|first1=P. D.\|last2=Han\|first2=L.\|date=1994-08-01\|title=Generalized cluster algorithms for frustrated spin models\|url=https://link.aps.org/doi/10.1103/PhysRevB.50.3058\|journal=Physical Review B\|volume=50\|issue=5\|pages=3058–3067\|doi=10.1103/PhysRevB.50.3058\|pmid=9976551\|arxiv=cond-mat/9402030\|bibcode=1994PhRvB..50.3058C\|s2cid=939709}}</ref> 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 ==		== Algorithm ==
Line 15:		Line 15:
	At zero temperature, or the <math>\beta \to \infty</math> limit, all the plaquettes will contain exactly one negative edge. In this case, on each checkered plaquette, the KBD algorithm will always [[Percolation theory\|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 (graph theory)\|cycle]].		At zero temperature, or the <math>\beta \to \infty</math> limit, all the plaquettes will contain exactly one negative edge. In this case, on each checkered plaquette, the KBD algorithm will always [[Percolation theory\|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 (graph theory)\|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 [[Homotopy\|contracted]] to a point in the [[Euler characteristic\|underlying surface]] that the lattice is [[Graph embedding\|embedded]] in.<ref>{{Cite journal\|~~last~~=Kandel\|~~first~~=Daniel\|last2=Ben-Av\|first2=Radel\|last3=Domany\|first3=Eytan\|date=1992-03-01\|title=Cluster Monte Carlo dynamics for the fully frustrated Ising model\|url=https://link.aps.org/doi/10.1103/PhysRevB.45.4700\|journal=Physical Review B\|volume=45\|issue=9\|pages=4700–4709\|doi=10.1103/PhysRevB.45.4700}}</ref> 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 [[Giant component\|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]].		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 [[Homotopy\|contracted]] to a point in the [[Euler characteristic\|underlying surface]] that the lattice is [[Graph embedding\|embedded]] in.<ref>{{Cite journal\|last1=Kandel\|first1=Daniel\|last2=Ben-Av\|first2=Radel\|last3=Domany\|first3=Eytan\|date=1992-03-01\|title=Cluster Monte Carlo dynamics for the fully frustrated Ising model\|url=https://link.aps.org/doi/10.1103/PhysRevB.45.4700\|journal=Physical Review B\|volume=45\|issue=9\|pages=4700–4709\|doi=10.1103/PhysRevB.45.4700\|pmid=10002105\|bibcode=1992PhRvB..45.4700K}}</ref> 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 [[Giant component\|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 ==		== References ==

OAbot: Open access bot: arxiv added to citation with #oabot.

2021-10-04T04:41:14Z

Open access bot: arxiv added to citation with #oabot.

← Previous revision		Revision as of 04:41, 4 October 2021
Line 5:		Line 5:

	== Motivation ==		== Motivation ==
	The [[Swendsen–Wang algorithm\|SW algorithm]] is the first non-local algorithm designed for efficient simulation of [[Ising model\|ferromagnetic spin models]].<ref>{{Cite journal\|last=Swendsen\|first=Robert H.\|last2=Wang\|first2=Jian-Sheng\|date=1987-01-12\|title=Nonuniversal critical dynamics in Monte Carlo simulations\|url=https://link.aps.org/doi/10.1103/PhysRevLett.58.86\|journal=Physical Review Letters\|volume=58\|issue=2\|pages=86–88\|doi=10.1103/PhysRevLett.58.86}}</ref> However, it is soon realized that the efficiency of the algorithm cannot be extended to [[Geometrical frustration\|frustrated systems]], due to an overly large [[Percolation critical exponents\|correlation length of the generated clusters]] with respect to the underlying spin system.<ref>{{Cite journal\|last=Cataudella\|first=V.\|date=1992-05-01\|title=Percolation transition in systems with frustation\|url=https://www.sciencedirect.com/science/article/pii/037843719290145G\|journal=Physica A: Statistical Mechanics and its Applications\|language=en\|volume=183\|issue=3\|pages=249–254\|doi=10.1016/0378-4371(92)90145-G\|issn=0378-4371}}</ref> 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,<ref>{{Cite journal\|last=Coddington\|first=P. D.\|last2=Han\|first2=L.\|date=1994-08-01\|title=Generalized cluster algorithms for frustrated spin models\|url=https://link.aps.org/doi/10.1103/PhysRevB.50.3058\|journal=Physical Review B\|volume=50\|issue=5\|pages=3058–3067\|doi=10.1103/PhysRevB.50.3058}}</ref> 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.		The [[Swendsen–Wang algorithm\|SW algorithm]] is the first non-local algorithm designed for efficient simulation of [[Ising model\|ferromagnetic spin models]].<ref>{{Cite journal\|last=Swendsen\|first=Robert H.\|last2=Wang\|first2=Jian-Sheng\|date=1987-01-12\|title=Nonuniversal critical dynamics in Monte Carlo simulations\|url=https://link.aps.org/doi/10.1103/PhysRevLett.58.86\|journal=Physical Review Letters\|volume=58\|issue=2\|pages=86–88\|doi=10.1103/PhysRevLett.58.86}}</ref> However, it is soon realized that the efficiency of the algorithm cannot be extended to [[Geometrical frustration\|frustrated systems]], due to an overly large [[Percolation critical exponents\|correlation length of the generated clusters]] with respect to the underlying spin system.<ref>{{Cite journal\|last=Cataudella\|first=V.\|date=1992-05-01\|title=Percolation transition in systems with frustation\|url=https://www.sciencedirect.com/science/article/pii/037843719290145G\|journal=Physica A: Statistical Mechanics and its Applications\|language=en\|volume=183\|issue=3\|pages=249–254\|doi=10.1016/0378-4371(92)90145-G\|issn=0378-4371}}</ref> 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,<ref>{{Cite journal\|last=Coddington\|first=P. D.\|last2=Han\|first2=L.\|date=1994-08-01\|title=Generalized cluster algorithms for frustrated spin models\|url=https://link.aps.org/doi/10.1103/PhysRevB.50.3058\|journal=Physical Review B\|volume=50\|issue=5\|pages=3058–3067\|doi=10.1103/PhysRevB.50.3058\|arxiv=cond-mat/9402030}}</ref> 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 ==		== Algorithm ==

Yanru pei: fixed reference formatting

2021-09-29T08:12:14Z

fixed reference formatting

← Previous revision		Revision as of 08:12, 29 September 2021
Line 5:		Line 5:

	== Motivation ==		== Motivation ==
	The [[Swendsen–Wang algorithm\|SW algorithm]] is the first non-local algorithm designed for efficient simulation of [[Ising model\|ferromagnetic spin models]] <ref>{{Cite journal\|last=Swendsen\|first=Robert H.\|last2=Wang\|first2=Jian-Sheng\|date=1987-01-12\|title=Nonuniversal critical dynamics in Monte Carlo simulations\|url=https://link.aps.org/doi/10.1103/PhysRevLett.58.86\|journal=Physical Review Letters\|volume=58\|issue=2\|pages=86–88\|doi=10.1103/PhysRevLett.58.86}}</ref>. However, it is soon realized that the efficiency of the algorithm cannot be extended to [[Geometrical frustration\|frustrated systems]], due to an overly large [[Percolation critical exponents\|correlation length of the generated clusters]] with respect to the underlying spin system <ref>{{Cite journal\|last=Cataudella\|first=V.\|date=1992-05-01\|title=Percolation transition in systems with frustation\|url=https://www.sciencedirect.com/science/article/pii/037843719290145G\|journal=Physica A: Statistical Mechanics and its Applications\|language=en\|volume=183\|issue=3\|pages=249–254\|doi=10.1016/0378-4371(92)90145-G\|issn=0378-4371}}</ref>. 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 <ref>{{Cite journal\|last=Coddington\|first=P. D.\|last2=Han\|first2=L.\|date=1994-08-01\|title=Generalized cluster algorithms for frustrated spin models\|url=https://link.aps.org/doi/10.1103/PhysRevB.50.3058\|journal=Physical Review B\|volume=50\|issue=5\|pages=3058–3067\|doi=10.1103/PhysRevB.50.3058}}</ref>, 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.		The [[Swendsen–Wang algorithm\|SW algorithm]] is the first non-local algorithm designed for efficient simulation of [[Ising model\|ferromagnetic spin models]].<ref>{{Cite journal\|last=Swendsen\|first=Robert H.\|last2=Wang\|first2=Jian-Sheng\|date=1987-01-12\|title=Nonuniversal critical dynamics in Monte Carlo simulations\|url=https://link.aps.org/doi/10.1103/PhysRevLett.58.86\|journal=Physical Review Letters\|volume=58\|issue=2\|pages=86–88\|doi=10.1103/PhysRevLett.58.86}}</ref> However, it is soon realized that the efficiency of the algorithm cannot be extended to [[Geometrical frustration\|frustrated systems]], due to an overly large [[Percolation critical exponents\|correlation length of the generated clusters]] with respect to the underlying spin system.<ref>{{Cite journal\|last=Cataudella\|first=V.\|date=1992-05-01\|title=Percolation transition in systems with frustation\|url=https://www.sciencedirect.com/science/article/pii/037843719290145G\|journal=Physica A: Statistical Mechanics and its Applications\|language=en\|volume=183\|issue=3\|pages=249–254\|doi=10.1016/0378-4371(92)90145-G\|issn=0378-4371}}</ref> 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,<ref>{{Cite journal\|last=Coddington\|first=P. D.\|last2=Han\|first2=L.\|date=1994-08-01\|title=Generalized cluster algorithms for frustrated spin models\|url=https://link.aps.org/doi/10.1103/PhysRevB.50.3058\|journal=Physical Review B\|volume=50\|issue=5\|pages=3058–3067\|doi=10.1103/PhysRevB.50.3058}}</ref> 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 ==		== 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 <ref name=":0" />. 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 <math>p = 1-e^{-4\beta}</math>, where <math>\beta</math> is the [[Boltzmann distribution\|inverse temperature]] of the spin model.		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.<ref name=":0" /> 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 <math>p = 1-e^{-4\beta}</math>, where <math>\beta</math> is the [[Boltzmann distribution\|inverse temperature]] of the spin model.

	The bonds will then form [[Random cluster model\|clusters]] on the lattice, on which the spins can be collectively flipped (either with the [[Swendsen–Wang algorithm\|SW]] rule or the [[Wolff algorithm\|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 [[Ergodicity\|ergodic]] algorithms like [[Glauber dynamics\|single spin-flip updates]].		The bonds will then form [[Random cluster model\|clusters]] on the lattice, on which the spins can be collectively flipped (either with the [[Swendsen–Wang algorithm\|SW]] rule or the [[Wolff algorithm\|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 [[Ergodicity\|ergodic]] algorithms like [[Glauber dynamics\|single spin-flip updates]].

Yanru pei: added references to previous removed sections

2021-09-29T08:09:29Z

added references to previous removed sections

← Previous revision		Revision as of 08:09, 29 September 2021
Line 2:		Line 2:
	{{refimprove\|date=May 2021}}		{{refimprove\|date=May 2021}}

	The '''KBD algorithm''' is a [[Swendsen–Wang algorithm\|cluster update algorithm]] designed for the [[Domino tiling\|fully frustrated Ising model]] in two dimensions,<ref>{{Cite journal\|last=Kandel\|first=Daniel\|last2=Ben-Av\|first2=Radel\|last3=Domany\|first3=Eytan\|date=1990-08-20\|title=Cluster dynamics for fully frustrated systems\|url=https://link.aps.org/doi/10.1103/PhysRevLett.65.941\|journal=Physical Review Letters\|volume=65\|issue=8\|pages=941–944\|doi=10.1103/PhysRevLett.65.941}}</ref> or more generally any two dimensional spin glass with frustrated plaquettes arranged in a [[Check (pattern)\|checkered pattern]].<ref>{{Cite journal\|last=Hamze\|first=Firas\|last2=Jacob\|first2=Darryl C.\|last3=Ochoa\|first3=Andrew J.\|last4=Perera\|first4=Dilina\|last5=Wang\|first5=Wenlong\|last6=Katzgraber\|first6=Helmut G.\|date=2018-04-13\|title=From near to eternity: Spin-glass planting, tiling puzzles, and constraint-satisfaction problems\|url=https://link.aps.org/doi/10.1103/PhysRevE.97.043303\|journal=Physical Review E\|volume=97\|issue=4\|pages=043303\|doi=10.1103/PhysRevE.97.043303\|doi-access=free}}</ref> 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.<ref>{{Cite journal\|last=Coddington\|first=P. D.\|last2=Han\|first2=L.\|date=1994-08-01\|title=Generalized cluster algorithms for frustrated spin models\|url=https://link.aps.org/doi/10.1103/PhysRevB.50.3058\|journal=Physical Review B\|volume=50\|issue=5\|pages=3058–3067\|doi=10.1103/PhysRevB.50.3058\|arxiv=cond-mat/9402030}}</ref> It is the inspiration for cluster algorithms used in [[Quantum Monte Carlo\|quantum monte carlo]] simulations.		The '''KBD algorithm''' is a [[Swendsen–Wang algorithm\|cluster update algorithm]] designed for the [[Domino tiling\|fully frustrated Ising model]] in two dimensions,<ref name=":0">{{Cite journal\|last=Kandel\|first=Daniel\|last2=Ben-Av\|first2=Radel\|last3=Domany\|first3=Eytan\|date=1990-08-20\|title=Cluster dynamics for fully frustrated systems\|url=https://link.aps.org/doi/10.1103/PhysRevLett.65.941\|journal=Physical Review Letters\|volume=65\|issue=8\|pages=941–944\|doi=10.1103/PhysRevLett.65.941}}</ref> or more generally any two dimensional spin glass with frustrated plaquettes arranged in a [[Check (pattern)\|checkered pattern]].<ref>{{Cite journal\|last=Hamze\|first=Firas\|last2=Jacob\|first2=Darryl C.\|last3=Ochoa\|first3=Andrew J.\|last4=Perera\|first4=Dilina\|last5=Wang\|first5=Wenlong\|last6=Katzgraber\|first6=Helmut G.\|date=2018-04-13\|title=From near to eternity: Spin-glass planting, tiling puzzles, and constraint-satisfaction problems\|url=https://link.aps.org/doi/10.1103/PhysRevE.97.043303\|journal=Physical Review E\|volume=97\|issue=4\|pages=043303\|doi=10.1103/PhysRevE.97.043303\|doi-access=free}}</ref> 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.<ref>{{Cite journal\|last=Coddington\|first=P. D.\|last2=Han\|first2=L.\|date=1994-08-01\|title=Generalized cluster algorithms for frustrated spin models\|url=https://link.aps.org/doi/10.1103/PhysRevB.50.3058\|journal=Physical Review B\|volume=50\|issue=5\|pages=3058–3067\|doi=10.1103/PhysRevB.50.3058\|arxiv=cond-mat/9402030}}</ref> It is the inspiration for cluster algorithms used in [[Quantum Monte Carlo\|quantum monte carlo]] simulations.

	== Motivation ==		== Motivation ==
	The [[Swendsen–Wang algorithm\|SW algorithm]] is the first non-local algorithm designed for efficient simulation of [[Ising model\|ferromagnetic spin models]]. However, it is soon realized that the efficiency of the algorithm cannot be extended to [[Geometrical frustration\|frustrated systems]], due to an overly large [[Percolation critical exponents\|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.		The [[Swendsen–Wang algorithm\|SW algorithm]] is the first non-local algorithm designed for efficient simulation of [[Ising model\|ferromagnetic spin models]] <ref>{{Cite journal\|last=Swendsen\|first=Robert H.\|last2=Wang\|first2=Jian-Sheng\|date=1987-01-12\|title=Nonuniversal critical dynamics in Monte Carlo simulations\|url=https://link.aps.org/doi/10.1103/PhysRevLett.58.86\|journal=Physical Review Letters\|volume=58\|issue=2\|pages=86–88\|doi=10.1103/PhysRevLett.58.86}}</ref>. However, it is soon realized that the efficiency of the algorithm cannot be extended to [[Geometrical frustration\|frustrated systems]], due to an overly large [[Percolation critical exponents\|correlation length of the generated clusters]] with respect to the underlying spin system <ref>{{Cite journal\|last=Cataudella\|first=V.\|date=1992-05-01\|title=Percolation transition in systems with frustation\|url=https://www.sciencedirect.com/science/article/pii/037843719290145G\|journal=Physica A: Statistical Mechanics and its Applications\|language=en\|volume=183\|issue=3\|pages=249–254\|doi=10.1016/0378-4371(92)90145-G\|issn=0378-4371}}</ref>. 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 <ref>{{Cite journal\|last=Coddington\|first=P. D.\|last2=Han\|first2=L.\|date=1994-08-01\|title=Generalized cluster algorithms for frustrated spin models\|url=https://link.aps.org/doi/10.1103/PhysRevB.50.3058\|journal=Physical Review B\|volume=50\|issue=5\|pages=3058–3067\|doi=10.1103/PhysRevB.50.3058}}</ref>, 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 ==		== 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 <math>p = 1-e^{-4\beta}</math>, where <math>\beta</math> is the [[Boltzmann distribution\|inverse temperature]] of the spin model.		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 <ref name=":0" />. 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 <math>p = 1-e^{-4\beta}</math>, where <math>\beta</math> is the [[Boltzmann distribution\|inverse temperature]] of the spin model.

	The bonds will then form [[Random cluster model\|clusters]] on the lattice, on which the spins can be collectively flipped (either with the SW rule or the [[Wolff algorithm\|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 [[Ergodicity\|ergodic]] algorithms like [[Glauber dynamics\|single spin-flip updates]].		The bonds will then form [[Random cluster model\|clusters]] on the lattice, on which the spins can be collectively flipped (either with the [[Swendsen–Wang algorithm\|SW]] rule or the [[Wolff algorithm\|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 [[Ergodicity\|ergodic]] algorithms like [[Glauber dynamics\|single spin-flip updates]].

	== Topological features ==		== Topological features ==

Uanfala: rv: the section is not unsourced (its sources are all listed in the lede), the article is not too technical (it's written precisely at the level of the sort of readers who would look up that very niche topic); no need for general category as the article is already included in the most relevant subcat

2021-09-29T07:14:06Z

rv: the section is *not* unsourced (its sources are all listed in the lede), the article is not too technical (it's written precisely at the level of the sort of readers who would look up that very niche topic); no need for general category as the article is already included in the most relevant subcat

@@ Line 1: / Line 1: @@
 {{Short description|Cluster update algorithm}}
-{{Technical|date=September 2021}}
+{{refimprove|date=May 2021}}
 The '''KBD algorithm''' is a [[Swendsen–Wang algorithm|cluster update algorithm]] designed for the [[Domino tiling|fully frustrated Ising model]] in two dimensions,<ref>{{Cite journal|last=Kandel|first=Daniel|last2=Ben-Av|first2=Radel|last3=Domany|first3=Eytan|date=1990-08-20|title=Cluster dynamics for fully frustrated systems|url=https://link.aps.org/doi/10.1103/PhysRevLett.65.941|journal=Physical Review Letters|volume=65|issue=8|pages=941–944|doi=10.1103/PhysRevLett.65.941}}</ref> or more generally any two dimensional spin glass with frustrated plaquettes arranged in a [[Check (pattern)|checkered pattern]].<ref>{{Cite journal|last=Hamze|first=Firas|last2=Jacob|first2=Darryl C.|last3=Ochoa|first3=Andrew J.|last4=Perera|first4=Dilina|last5=Wang|first5=Wenlong|last6=Katzgraber|first6=Helmut G.|date=2018-04-13|title=From near to eternity: Spin-glass planting, tiling puzzles, and constraint-satisfaction problems|url=https://link.aps.org/doi/10.1103/PhysRevE.97.043303|journal=Physical Review E|volume=97|issue=4|pages=043303|doi=10.1103/PhysRevE.97.043303|doi-access=free}}</ref> 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.<ref>{{Cite journal|last=Coddington|first=P. D.|last2=Han|first2=L.|date=1994-08-01|title=Generalized cluster algorithms for frustrated spin models|url=https://link.aps.org/doi/10.1103/PhysRevB.50.3058|journal=Physical Review B|volume=50|issue=5|pages=3058–3067|doi=10.1103/PhysRevB.50.3058|arxiv=cond-mat/9402030}}</ref> It is the inspiration for cluster algorithms used in [[Quantum Monte Carlo|quantum monte carlo]] simulations.
 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 [[Homotopy|contracted]] to a point in the [[Euler characteristic|underlying surface]] that the lattice is [[Graph embedding|embedded]] in.<ref>{{Cite journal|last=Kandel|first=Daniel|last2=Ben-Av|first2=Radel|last3=Domany|first3=Eytan|date=1992-03-01|title=Cluster Monte Carlo dynamics for the fully frustrated Ising model|url=https://link.aps.org/doi/10.1103/PhysRevB.45.4700|journal=Physical Review B|volume=45|issue=9|pages=4700–4709|doi=10.1103/PhysRevB.45.4700}}</ref> 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 [[Giant component|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]].
@@ Line 13: / Line 24: @@
 [[Category:Statistical mechanics]]
 [[Category:Monte Carlo methods]]

JBchrch: Added {{algorithm-stub}} using a tool

2021-09-28T22:34:58Z

Added {{algorithm-stub}} using a tool

← Previous revision		Revision as of 22:34, 28 September 2021
Line 14:		Line 14:
	[[Category:Monte Carlo methods]]		[[Category:Monte Carlo methods]]
	[[Category:Algorithms]]		[[Category:Algorithms]]


			{{algorithm-stub}}

JBchrch: added Category:Algorithms using HotCat

2021-09-28T22:33:55Z

added Category:Algorithms using HotCat

← Previous revision		Revision as of 22:33, 28 September 2021
Line 13:		Line 13:
	[[Category:Statistical mechanics]]		[[Category:Statistical mechanics]]
	[[Category:Monte Carlo methods]]		[[Category:Monte Carlo methods]]
			[[Category:Algorithms]]

JBchrch: Added {{Technical}}; and removed {{More citations needed}} tags

2021-09-28T22:32:35Z

Added {{Technical}}; and removed {{More citations needed}} tags

← Previous revision		Revision as of 22:32, 28 September 2021
Line 1:		Line 1:
	{{Short description\|Cluster update algorithm}}		{{Short description\|Cluster update algorithm}}
	{{~~refimprove~~\|date=~~May~~ 2021}}		{{Technical\|date=September 2021}}

	The '''KBD algorithm''' is a [[Swendsen–Wang algorithm\|cluster update algorithm]] designed for the [[Domino tiling\|fully frustrated Ising model]] in two dimensions,<ref>{{Cite journal\|last=Kandel\|first=Daniel\|last2=Ben-Av\|first2=Radel\|last3=Domany\|first3=Eytan\|date=1990-08-20\|title=Cluster dynamics for fully frustrated systems\|url=https://link.aps.org/doi/10.1103/PhysRevLett.65.941\|journal=Physical Review Letters\|volume=65\|issue=8\|pages=941–944\|doi=10.1103/PhysRevLett.65.941}}</ref> or more generally any two dimensional spin glass with frustrated plaquettes arranged in a [[Check (pattern)\|checkered pattern]].<ref>{{Cite journal\|last=Hamze\|first=Firas\|last2=Jacob\|first2=Darryl C.\|last3=Ochoa\|first3=Andrew J.\|last4=Perera\|first4=Dilina\|last5=Wang\|first5=Wenlong\|last6=Katzgraber\|first6=Helmut G.\|date=2018-04-13\|title=From near to eternity: Spin-glass planting, tiling puzzles, and constraint-satisfaction problems\|url=https://link.aps.org/doi/10.1103/PhysRevE.97.043303\|journal=Physical Review E\|volume=97\|issue=4\|pages=043303\|doi=10.1103/PhysRevE.97.043303\|doi-access=free}}</ref> 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.<ref>{{Cite journal\|last=Coddington\|first=P. D.\|last2=Han\|first2=L.\|date=1994-08-01\|title=Generalized cluster algorithms for frustrated spin models\|url=https://link.aps.org/doi/10.1103/PhysRevB.50.3058\|journal=Physical Review B\|volume=50\|issue=5\|pages=3058–3067\|doi=10.1103/PhysRevB.50.3058\|arxiv=cond-mat/9402030}}</ref> It is the inspiration for cluster algorithms used in [[Quantum Monte Carlo\|quantum monte carlo]] simulations.		The '''KBD algorithm''' is a [[Swendsen–Wang algorithm\|cluster update algorithm]] designed for the [[Domino tiling\|fully frustrated Ising model]] in two dimensions,<ref>{{Cite journal\|last=Kandel\|first=Daniel\|last2=Ben-Av\|first2=Radel\|last3=Domany\|first3=Eytan\|date=1990-08-20\|title=Cluster dynamics for fully frustrated systems\|url=https://link.aps.org/doi/10.1103/PhysRevLett.65.941\|journal=Physical Review Letters\|volume=65\|issue=8\|pages=941–944\|doi=10.1103/PhysRevLett.65.941}}</ref> or more generally any two dimensional spin glass with frustrated plaquettes arranged in a [[Check (pattern)\|checkered pattern]].<ref>{{Cite journal\|last=Hamze\|first=Firas\|last2=Jacob\|first2=Darryl C.\|last3=Ochoa\|first3=Andrew J.\|last4=Perera\|first4=Dilina\|last5=Wang\|first5=Wenlong\|last6=Katzgraber\|first6=Helmut G.\|date=2018-04-13\|title=From near to eternity: Spin-glass planting, tiling puzzles, and constraint-satisfaction problems\|url=https://link.aps.org/doi/10.1103/PhysRevE.97.043303\|journal=Physical Review E\|volume=97\|issue=4\|pages=043303\|doi=10.1103/PhysRevE.97.043303\|doi-access=free}}</ref> 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.<ref>{{Cite journal\|last=Coddington\|first=P. D.\|last2=Han\|first2=L.\|date=1994-08-01\|title=Generalized cluster algorithms for frustrated spin models\|url=https://link.aps.org/doi/10.1103/PhysRevB.50.3058\|journal=Physical Review B\|volume=50\|issue=5\|pages=3058–3067\|doi=10.1103/PhysRevB.50.3058\|arxiv=cond-mat/9402030}}</ref> It is the inspiration for cluster algorithms used in [[Quantum Monte Carlo\|quantum monte carlo]] simulations.