2857:
2355:
3329:
2852:{\displaystyle {\frac {P_{\lbrace \sigma \rbrace \rightarrow \lbrace \sigma '\rbrace }}{P_{\lbrace \sigma '\rbrace \rightarrow \lbrace \sigma \rbrace }}}={\frac {Pr\left(\lbrace \sigma '\rbrace |B.C.\right)Pr\left(B.C.|\lbrace \sigma \rbrace \right)}{Pr\left(\lbrace \sigma \rbrace |B.C.\right)Pr\left(B.C.|\lbrace \sigma '\rbrace \right)}}={\frac {p\cdot \exp \left}{p\cdot \exp \left}}=e^{-\beta \Delta E}}
2864:
3377:) is that the correlation length divergence is strictly related to the formation of percolation clusters, which are flipped together. In this way the relaxation time is significantly reduced. Another way to view this is through the correspondence between the spin statistics and cluster statistics in the
2287:
The SW algorithm does however satisfy detailed-balance. To show this, we note that every transition between two Ising spin states must pass through some bond configuration in the percolation representation. Let's fix a particular bond configuration: what matters in comparing the probabilities related
2283:
Ergodicity means that it is possible to transit from any initial state to any final state with a finite number of updates. It has been shown that the SW algorithm is not ergodic in general (in the thermodynamic limit). Thus in practice, the SW algorithm is usually used in conjunction with single
2250:
After assigning the bond variables, we identify the same-spin clusters formed by connected sites and make an inversion of all the variables in the cluster with probability 1/2. At the following time step we have a new starting Ising configuration, which will produce a new clustering and a new
1625:
3324:{\displaystyle \Delta E=-\sum \limits _{<l,m>}J_{lm}\left(\sigma '_{l}\sigma '_{m}-\sigma _{l}\sigma _{m}\right)=-\sum \limits _{<l,m>}J_{lm}\left=-2\sum \limits _{<l,m>}J_{lm}\left(\delta _{\sigma '_{l},\sigma '_{m}}-\delta _{\sigma _{l},\sigma _{m}}\right)}
1473:
2054:
2058:
Since the first term contains a restriction on the spin values whereas there is no restriction in the second term, the weighting factors (properly normalized) can be interpreted as probabilities of forming/not forming a link between the sites:
1338:
1764:
1104:
1177:
3334:
This is valid for every bond configuration the system can pass through during its evolution, so detailed balance is satisfied for the total transition probability. This proves that the algorithm is correct.
1480:
3382:
3407:
The first approach is to extend the bond-formation rules to more non-local cells, and the second approach is to generate clusters based on more relevant order parameters. In the first case, we have the
2150:
1875:
83:), as increasing the size of the system in order to reduce finite-size effects has the disadvantage of requiring a far larger number of moves to reach thermal equilibrium. Indeed the correlation time
3343:
Although not analytically clear from the original paper, the reason why all the values of z obtained with the SW algorithm are much lower than the exact lower bound for single-spin-flip algorithms (
3404:
in the presence of frustrated interactions. Currently, there are two main approaches to addressing this problem, such that the efficiency of cluster algorithms is extended to frustrated systems.
558:
1347:
394:
2330:
for each missing bond between neighboring spins with the same value; the probability of going to a certain Ising configuration compatible with a given bond configuration is uniform (say
967:
849:
1885:
63:
model through percolation models of connecting bonds, due to
Fortuin and Kasteleyn. It has been generalized by Barbu and Zhu to arbitrary sampling probabilities by viewing it as a
3375:
2328:
2244:
2197:
1006:
180:
516:
433:
154:
1225:
737:
651:
236:
262:
210:
288:
128:
101:
343:
2348:
1220:
1200:
473:
453:
3401:
1110:
3416:, where the decision of opening bonds are made on each plaquette, arranged in a checkerboard pattern on the square lattice. In the second case, we have
1631:
1016:
1118:
1620:{\displaystyle Z_{n,m}^{diff}=\sum \limits _{\lbrace \sigma \rbrace }e^{-\beta H_{nm}}\left(1-\delta _{\sigma _{n},\sigma _{m}}\right).}
64:
2062:
1773:
29:
3914:
3397:
75:
The problem of the critical slowing-down affecting local processes is of fundamental importance in the study of second-order
521:
3909:
1468:{\displaystyle Z_{n,m}^{same}=\sum \limits _{\lbrace \sigma \rbrace }e^{-\beta H_{nm}}\delta _{\sigma _{n},\sigma _{m}}}
2260:
It can be shown that this algorithm leads to equilibrium configurations. To show this, we interpret the algorithm as a
3919:
348:
308:. The update is done on a "cluster" of spin variables connected by open bond variables that are generated through a
3924:
41:
3733:
Swendsen, Robert H.; Wang, Jian-Sheng (1987-01-12). "Nonuniversal critical dynamics in Monte Carlo simulations".
3424:, where the clusters are generated based on spin overlaps, which is believed to be the relevant order parameter.
854:
304:
The algorithm is non-local in the sense that a single sweep updates a collection of spin variables based on the
3381:. Some mathematically rigorous results on the mixing time of this process have been obtained by Guo and Jerrum
2049:{\displaystyle Z=\left(e^{\beta J_{nm}}-e^{-\beta J_{nm}}\right)Z_{n,m}^{same}+e^{-\beta J_{nm}}Z_{n,m}^{ind}.}
742:
3393:
2277:
1011:
This probability distribution has been derived in the following way: the
Hamiltonian of the Ising model is
2273:
25:
3346:
319:
Starting from a given configuration of spins, we associate to each pair of nearest neighbours on sites
2152:
The process can be easily adapted to antiferromagnetic spin systems, as it is sufficient to eliminate
3827:
3790:
3742:
3700:
3643:
3596:
3541:
3433:
3417:
3378:
2291:
305:
299:
186:. SW algorithm was the first to produce unusually small values for the dynamical critical exponents:
56:
37:
2202:
2155:
3888:
3565:
3510:
3438:
1333:{\displaystyle H_{nm}=\sum \limits _{<i,j>\neq <n,m>}-J_{i,j}\sigma _{i}\sigma _{j}.}
975:
309:
51:
and Potts models, and it was later generalized to other systems as well, such as the XY model by
3585:"Generalization of the Fortuin-Kasteleyn-Swendsen-Wang representation and Monte Carlo algorithm"
159:
564:). These values are assigned according to the following (conditional) probability distribution:
482:
399:
133:
3880:
3872:
3855:
Barbu, A. (2005). "Generalizing
Swendsen-Wang to sampling arbitrary posterior probabilities".
3843:
3806:
3766:
3758:
3716:
3669:
3612:
3557:
3502:
3494:
656:
570:
3448:
215:
3864:
3835:
3798:
3750:
3708:
3659:
3651:
3604:
3549:
3486:
2269:
241:
189:
76:
3453:
267:
106:
86:
3443:
183:
52:
33:
322:
3831:
3794:
3746:
3704:
3647:
3600:
3545:
3631:
2333:
1205:
1185:
458:
438:
3688:
2350:). So the ratio of the transition probabilities of going from one state to another is
2284:
spin-flip algorithms such as the
Metropolis–Hastings algorithm to achieve ergodicity.
3903:
3839:
3802:
3569:
3413:
3409:
315:
Consider a typical ferromagnetic Ising model with only nearest-neighbor interaction.
3584:
182:, this is a major limitation in the size of the systems that can be studied through
2261:
3892:
3630:
Cataudella, V.; Franzese, G.; Nicodemi, M.; Scala, A.; Coniglio, A. (1994-03-07).
3514:
1759:{\displaystyle Z=e^{\beta J_{nm}}Z_{n,m}^{same}+e^{-\beta J_{nm}}Z_{n,m}^{diff}.}
3818:
Wang, Jian-Sheng; Swendsen, Robert H. (1990). "Cluster Monte Carlo algorithms".
3655:
80:
60:
48:
3712:
3754:
3553:
3421:
2265:
3876:
3847:
3810:
3762:
3608:
3561:
3498:
3474:
21:
3884:
3868:
3770:
3720:
3673:
3506:
3490:
1099:{\displaystyle H=\sum \limits _{<i,j>}-J_{i,j}\sigma _{i}\sigma _{j}}
67:
and computing the acceptance probability of the proposed Monte Carlo move.
3863:(8). Institute of Electrical and Electronics Engineers (IEEE): 1239–1253.
3616:
3529:
3475:"Generalizing Swendsen-Wang to sampling arbitrary posterior probabilities"
3781:
Fortuin, C.M.; Kasteleyn, P.W. (1972). "On the random-cluster model".
3664:
3632:"Critical clusters and efficient dynamics for frustrated spin models"
1172:{\displaystyle Z=\sum \limits _{\lbrace \sigma \rbrace }e^{-\beta H}}
3777:
Kasteleyn P. W. and
Fortuin (1969) J. Phys. Soc. Jpn. Suppl. 26s:11
2246:(as suggested by the change of sign in the interaction constant).
156:
or greater; since, to be accurate, the simulation time must be
3857:
IEEE Transactions on
Pattern Analysis and Machine Intelligence
3479:
IEEE Transactions on
Pattern Analysis and Machine Intelligence
3687:
Kandel, Daniel; Ben-Av, Radel; Domany, Eytan (1990-08-20).
2145:{\displaystyle P_{<n,m>\;link}=1-e^{-2\beta J_{nm}}.}
3449:
http://www.hpjava.org/theses/shko/thesis_paper/node69.html
1870:{\displaystyle Z_{nm}^{ind}=Z_{n,m}^{same}+Z_{n,m}^{diff}}
1182:
Consider the interaction between a pair of selected sites
2268:(when used together with other algorithms) and satisfies
3454:
http://www-fcs.acs.i.kyoto-u.ac.jp/~harada/monte-en.html
3530:"The Swendsen–Wang Process Does Not Always Mix Rapidly"
312:
process, based on the interaction states of the spins.
1222:
3820:
Physica A: Statistical
Mechanics and Its Applications
3349:
2867:
2358:
2336:
2294:
2205:
2158:
2065:
1888:
1776:
1634:
1483:
1350:
1228:
1208:
1188:
1121:
1019:
978:
857:
745:
659:
573:
524:
485:
461:
441:
402:
351:
325:
270:
244:
218:
192:
162:
136:
109:
89:
553:{\displaystyle \sigma _{n}{\text{ and }}\sigma _{m}}
55:
and particles of fluids. The key ingredient was the
3369:
3323:
2851:
2342:
2322:
2238:
2191:
2144:
2048:
1869:
1758:
1619:
1467:
1332:
1214:
1194:
1171:
1098:
1000:
961:
843:
731:
645:
552:
510:
467:
447:
427:
388:
337:
282:
256:
230:
204:
174:
148:
122:
95:
3583:Edwards, Robert G.; Sokal, Alan D. (1988-09-15).
3689:"Cluster dynamics for fully frustrated systems"
3528:Gore, Vivek K.; Jerrum, Mark R. (1999-10-01).
396:which is interpreted in the following way: if
389:{\displaystyle b_{n,m}\in \lbrace 0,1\rbrace }
3741:(2). American Physical Society (APS): 86–88.
3473:Barbu, Adrian; Zhu, Song-Chun (August 2005).
3392:The algorithm is not efficient in simulating
8:
2607:
2596:
2543:
2537:
2516:
2510:
2457:
2446:
2422:
2416:
2410:
2399:
2389:
2378:
2372:
2366:
1528:
1522:
1395:
1389:
1139:
1133:
383:
371:
47:The original algorithm was designed for the
1880:the partition function can be rewritten as
962:{\displaystyle P\left=1-e^{-2\beta J_{nm}}}
2086:
518:then there is a link connecting the spins
3663:
3359:
3348:
3308:
3295:
3290:
3272:
3256:
3251:
3233:
3211:
3180:
3167:
3162:
3136:
3123:
3118:
3095:
3079:
3074:
3045:
3029:
3024:
3006:
2984:
2963:
2953:
2937:
2924:
2906:
2884:
2866:
2834:
2810:
2795:
2779:
2774:
2752:
2706:
2694:
2681:
2676:
2654:
2621:
2591:
2546:
2505:
2460:
2432:
2398:
2365:
2359:
2357:
2335:
2305:
2293:
2221:
2210:
2204:
2174:
2163:
2157:
2128:
2114:
2070:
2064:
2031:
2020:
2005:
1994:
1972:
1961:
1941:
1930:
1912:
1904:
1887:
1852:
1841:
1819:
1808:
1789:
1781:
1775:
1738:
1727:
1712:
1701:
1679:
1668:
1653:
1645:
1633:
1601:
1588:
1583:
1548:
1537:
1521:
1499:
1488:
1482:
1457:
1444:
1439:
1415:
1404:
1388:
1366:
1355:
1349:
1321:
1311:
1295:
1258:
1233:
1227:
1207:
1187:
1148:
1132:
1120:
1090:
1080:
1064:
1039:
1018:
983:
977:
948:
934:
910:
897:
888:
870:
856:
844:{\displaystyle P\left=e^{-2\beta J_{nm}}}
830:
816:
798:
785:
776:
758:
744:
712:
699:
690:
672:
658:
626:
613:
604:
586:
572:
544:
535:
529:
523:
490:
484:
460:
440:
407:
401:
356:
350:
324:
269:
243:
217:
191:
161:
135:
114:
108:
88:
1008:is the ferromagnetic coupling strength.
435:then there is no link between the sites
3465:
264:for the 3D Ising model, as opposed to
79:(like ferromagnetic transition in the
7:
3402:correlation length of the spin model
3208:
2981:
2881:
2749:
2651:
1518:
1385:
1255:
1129:
1036:
59:, a representation of the Ising or
3398:correlation length of the clusters
3370:{\displaystyle z\geq \gamma /\nu }
2868:
2841:
2264:, and show that the chain is both
20:is the first non-local or cluster
14:
1342:Define also the restricted sums:
306:Fortuin–Kasteleyn representation
2323:{\displaystyle q=e^{-2\beta J}}
2288:to it is the number of factors
3534:Journal of Statistical Physics
2592:
2547:
2506:
2461:
2413:
2375:
2239:{\displaystyle Z_{n,m}^{diff}}
2192:{\displaystyle Z_{n,m}^{same}}
1563:
1557:
1430:
1424:
1248:
1242:
1164:
1158:
1029:
1023:
889:
777:
691:
605:
1:
65:Metropolis–Hastings algorithm
18:Swendsen–Wang algorithm
3840:10.1016/0378-4371(90)90275-w
3803:10.1016/0031-8914(72)90045-6
3414:fully-frustrated Ising model
3379:Edwards-Sokal representation
2272:, such that the equilibrium
32:. It has been introduced by
3826:(3). Elsevier BV: 565–579.
3789:(4). Elsevier BV: 536–564.
3656:10.1103/PhysRevLett.72.1541
1001:{\displaystyle J_{nm}>0}
238:for standard simulations);
3941:
3713:10.1103/PhysRevLett.65.941
297:
290:for standard simulations.
175:{\displaystyle t\gg \tau }
3755:10.1103/physrevlett.58.86
511:{\displaystyle b_{n,m}=1}
428:{\displaystyle b_{n,m}=0}
149:{\displaystyle z\simeq 2}
3609:10.1103/PhysRevD.38.2009
732:{\displaystyle P\left=0}
646:{\displaystyle P\left=1}
212:for the 2D Ising model (
3735:Physical Review Letters
3693:Physical Review Letters
3636:Physical Review Letters
3554:10.1023/A:1004610900745
2278:stationary distribution
1768:Introduce the quantity
231:{\displaystyle z=2.125}
28:for large systems near
3869:10.1109/tpami.2005.161
3491:10.1109/TPAMI.2005.161
3371:
3325:
2853:
2344:
2324:
2274:Boltzmann distribution
2240:
2193:
2146:
2050:
1871:
1760:
1621:
1469:
1334:
1216:
1196:
1173:
1100:
1002:
963:
845:
733:
647:
554:
512:
469:
449:
429:
390:
339:
284:
258:
257:{\displaystyle z=0.75}
232:
206:
205:{\displaystyle z=0.35}
176:
150:
124:
97:
26:Monte Carlo simulation
3915:Statistical mechanics
3372:
3326:
2854:
2345:
2325:
2251:collective spin-flip.
2241:
2194:
2147:
2051:
1872:
1761:
1622:
1470:
1335:
1217:
1197:
1174:
1101:
1003:
964:
846:
734:
648:
555:
513:
470:
450:
430:
391:
340:
285:
283:{\displaystyle z=2.0}
259:
233:
207:
177:
151:
125:
123:{\displaystyle L^{z}}
103:usually increases as
98:
96:{\displaystyle \tau }
3434:Random cluster model
3420:for low-dimensional
3418:replica cluster move
3347:
2865:
2356:
2334:
2292:
2203:
2156:
2063:
1886:
1774:
1632:
1481:
1348:
1226:
1206:
1186:
1119:
1017:
976:
855:
743:
657:
571:
522:
483:
459:
439:
400:
349:
323:
300:Random cluster model
268:
242:
216:
190:
160:
134:
107:
87:
57:random cluster model
3910:Monte Carlo methods
3832:1990PhyA..167..565W
3795:1972Phy....57..536F
3747:1987PhRvL..58...86S
3705:1990PhRvL..65..941K
3648:1994PhRvL..72.1541C
3601:1988PhRvD..38.2009E
3546:1999JSP....97...67G
3400:is larger than the
3280:
3264:
3103:
3087:
3053:
3037:
2945:
2932:
2803:
2787:
2235:
2188:
2042:
1986:
1866:
1833:
1800:
1752:
1693:
1513:
1380:
338:{\displaystyle n,m}
3920:Critical phenomena
3439:Monte Carlo method
3394:frustrated systems
3367:
3321:
3268:
3252:
3228:
3091:
3075:
3041:
3025:
3001:
2933:
2920:
2901:
2849:
2791:
2775:
2769:
2671:
2340:
2320:
2236:
2206:
2189:
2159:
2142:
2046:
2016:
1957:
1867:
1837:
1804:
1777:
1756:
1723:
1664:
1617:
1532:
1484:
1465:
1399:
1351:
1330:
1287:
1212:
1192:
1169:
1143:
1111:partition function
1096:
1056:
998:
959:
841:
729:
643:
550:
508:
465:
445:
425:
386:
345:a random variable
335:
280:
254:
228:
202:
172:
146:
120:
93:
3925:Phase transitions
3642:(10): 1541–1544.
3589:Physical Review D
3207:
2980:
2880:
2825:
2748:
2650:
2616:
2427:
2343:{\displaystyle p}
1517:
1384:
1272:>≠ <
1254:
1215:{\displaystyle m}
1195:{\displaystyle n}
1128:
1035:
538:
468:{\displaystyle m}
448:{\displaystyle n}
77:phase transitions
3932:
3896:
3851:
3814:
3774:
3725:
3724:
3684:
3678:
3677:
3667:
3627:
3621:
3620:
3595:(6): 2009–2012.
3580:
3574:
3573:
3525:
3519:
3518:
3485:(8): 1239–1253.
3470:
3376:
3374:
3373:
3368:
3363:
3330:
3328:
3327:
3322:
3320:
3316:
3315:
3314:
3313:
3312:
3300:
3299:
3282:
3281:
3276:
3260:
3241:
3240:
3227:
3197:
3193:
3192:
3188:
3187:
3186:
3185:
3184:
3172:
3171:
3143:
3142:
3141:
3140:
3128:
3127:
3110:
3106:
3105:
3104:
3099:
3083:
3055:
3054:
3049:
3033:
3014:
3013:
3000:
2973:
2969:
2968:
2967:
2958:
2957:
2941:
2928:
2914:
2913:
2900:
2858:
2856:
2855:
2850:
2848:
2847:
2826:
2824:
2823:
2819:
2818:
2817:
2805:
2804:
2799:
2783:
2768:
2720:
2719:
2715:
2714:
2713:
2701:
2700:
2699:
2698:
2686:
2685:
2670:
2622:
2617:
2615:
2614:
2610:
2606:
2595:
2567:
2563:
2550:
2524:
2523:
2519:
2509:
2481:
2477:
2464:
2456:
2433:
2428:
2426:
2425:
2409:
2393:
2392:
2388:
2360:
2349:
2347:
2346:
2341:
2329:
2327:
2326:
2321:
2319:
2318:
2276:is equal to the
2270:detailed balance
2245:
2243:
2242:
2237:
2234:
2220:
2198:
2196:
2195:
2190:
2187:
2173:
2151:
2149:
2148:
2143:
2138:
2137:
2136:
2135:
2100:
2099:
2055:
2053:
2052:
2047:
2041:
2030:
2015:
2014:
2013:
2012:
1985:
1971:
1956:
1952:
1951:
1950:
1949:
1948:
1922:
1921:
1920:
1919:
1876:
1874:
1873:
1868:
1865:
1851:
1832:
1818:
1799:
1788:
1765:
1763:
1762:
1757:
1751:
1737:
1722:
1721:
1720:
1719:
1692:
1678:
1663:
1662:
1661:
1660:
1626:
1624:
1623:
1618:
1613:
1609:
1608:
1607:
1606:
1605:
1593:
1592:
1567:
1566:
1556:
1555:
1531:
1512:
1498:
1474:
1472:
1471:
1466:
1464:
1463:
1462:
1461:
1449:
1448:
1434:
1433:
1423:
1422:
1398:
1379:
1365:
1339:
1337:
1336:
1331:
1326:
1325:
1316:
1315:
1306:
1305:
1286:
1241:
1240:
1221:
1219:
1218:
1213:
1201:
1199:
1198:
1193:
1178:
1176:
1175:
1170:
1168:
1167:
1142:
1105:
1103:
1102:
1097:
1095:
1094:
1085:
1084:
1075:
1074:
1055:
1007:
1005:
1004:
999:
991:
990:
968:
966:
965:
960:
958:
957:
956:
955:
920:
916:
915:
914:
902:
901:
892:
881:
880:
850:
848:
847:
842:
840:
839:
838:
837:
808:
804:
803:
802:
790:
789:
780:
769:
768:
738:
736:
735:
730:
722:
718:
717:
716:
704:
703:
694:
683:
682:
652:
650:
649:
644:
636:
632:
631:
630:
618:
617:
608:
597:
596:
559:
557:
556:
551:
549:
548:
539:
536:
534:
533:
517:
515:
514:
509:
501:
500:
474:
472:
471:
466:
454:
452:
451:
446:
434:
432:
431:
426:
418:
417:
395:
393:
392:
387:
367:
366:
344:
342:
341:
336:
289:
287:
286:
281:
263:
261:
260:
255:
237:
235:
234:
229:
211:
209:
208:
203:
184:local algorithms
181:
179:
178:
173:
155:
153:
152:
147:
129:
127:
126:
121:
119:
118:
102:
100:
99:
94:
3940:
3939:
3935:
3934:
3933:
3931:
3930:
3929:
3900:
3899:
3854:
3817:
3780:
3732:
3729:
3728:
3686:
3685:
3681:
3629:
3628:
3624:
3582:
3581:
3577:
3527:
3526:
3522:
3472:
3471:
3467:
3462:
3444:Wolff algorithm
3430:
3390:
3388:Generalizations
3345:
3344:
3341:
3304:
3291:
3286:
3247:
3246:
3242:
3229:
3176:
3163:
3158:
3151:
3147:
3132:
3119:
3114:
3070:
3063:
3059:
3020:
3019:
3015:
3002:
2959:
2949:
2919:
2915:
2902:
2863:
2862:
2830:
2806:
2770:
2738:
2734:
2721:
2702:
2690:
2677:
2672:
2640:
2636:
2623:
2599:
2578:
2574:
2536:
2532:
2525:
2492:
2488:
2449:
2445:
2441:
2434:
2402:
2394:
2381:
2361:
2354:
2353:
2332:
2331:
2301:
2290:
2289:
2258:
2201:
2200:
2154:
2153:
2124:
2110:
2066:
2061:
2060:
2001:
1990:
1937:
1926:
1908:
1900:
1899:
1895:
1884:
1883:
1772:
1771:
1708:
1697:
1649:
1641:
1630:
1629:
1597:
1584:
1579:
1572:
1568:
1544:
1533:
1479:
1478:
1453:
1440:
1435:
1411:
1400:
1346:
1345:
1317:
1307:
1291:
1229:
1224:
1223:
1204:
1203:
1184:
1183:
1144:
1117:
1116:
1086:
1076:
1060:
1015:
1014:
979:
974:
973:
970:
944:
930:
906:
893:
866:
865:
861:
853:
852:
826:
812:
794:
781:
754:
753:
749:
741:
740:
708:
695:
668:
667:
663:
655:
654:
622:
609:
582:
581:
577:
569:
568:
540:
537: and
525:
520:
519:
486:
481:
480:
457:
456:
437:
436:
403:
398:
397:
352:
347:
346:
321:
320:
302:
296:
266:
265:
240:
239:
214:
213:
188:
187:
158:
157:
132:
131:
110:
105:
104:
85:
84:
73:
53:Wolff algorithm
42:Carnegie Mellon
38:Jian-Sheng Wang
34:Robert Swendsen
12:
11:
5:
3938:
3936:
3928:
3927:
3922:
3917:
3912:
3902:
3901:
3898:
3897:
3852:
3815:
3778:
3775:
3727:
3726:
3699:(8): 941–944.
3679:
3622:
3575:
3520:
3464:
3463:
3461:
3458:
3457:
3456:
3451:
3446:
3441:
3436:
3429:
3426:
3396:, because the
3389:
3386:
3366:
3362:
3358:
3355:
3352:
3340:
3337:
3319:
3311:
3307:
3303:
3298:
3294:
3289:
3285:
3279:
3275:
3271:
3267:
3263:
3259:
3255:
3250:
3245:
3239:
3236:
3232:
3226:
3223:
3220:
3217:
3214:
3210:
3206:
3203:
3200:
3196:
3191:
3183:
3179:
3175:
3170:
3166:
3161:
3157:
3154:
3150:
3146:
3139:
3135:
3131:
3126:
3122:
3117:
3113:
3109:
3102:
3098:
3094:
3090:
3086:
3082:
3078:
3073:
3069:
3066:
3062:
3058:
3052:
3048:
3044:
3040:
3036:
3032:
3028:
3023:
3018:
3012:
3009:
3005:
2999:
2996:
2993:
2990:
2987:
2983:
2979:
2976:
2972:
2966:
2962:
2956:
2952:
2948:
2944:
2940:
2936:
2931:
2927:
2923:
2918:
2912:
2909:
2905:
2899:
2896:
2893:
2890:
2887:
2883:
2879:
2876:
2873:
2870:
2846:
2843:
2840:
2837:
2833:
2829:
2822:
2816:
2813:
2809:
2802:
2798:
2794:
2790:
2786:
2782:
2778:
2773:
2767:
2764:
2761:
2758:
2755:
2751:
2747:
2744:
2741:
2737:
2733:
2730:
2727:
2724:
2718:
2712:
2709:
2705:
2697:
2693:
2689:
2684:
2680:
2675:
2669:
2666:
2663:
2660:
2657:
2653:
2649:
2646:
2643:
2639:
2635:
2632:
2629:
2626:
2620:
2613:
2609:
2605:
2602:
2598:
2594:
2590:
2587:
2584:
2581:
2577:
2573:
2570:
2566:
2562:
2559:
2556:
2553:
2549:
2545:
2542:
2539:
2535:
2531:
2528:
2522:
2518:
2515:
2512:
2508:
2504:
2501:
2498:
2495:
2491:
2487:
2484:
2480:
2476:
2473:
2470:
2467:
2463:
2459:
2455:
2452:
2448:
2444:
2440:
2437:
2431:
2424:
2421:
2418:
2415:
2412:
2408:
2405:
2401:
2397:
2391:
2387:
2384:
2380:
2377:
2374:
2371:
2368:
2364:
2339:
2317:
2314:
2311:
2308:
2304:
2300:
2297:
2280:of the chain.
2257:
2254:
2253:
2252:
2233:
2230:
2227:
2224:
2219:
2216:
2213:
2209:
2186:
2183:
2180:
2177:
2172:
2169:
2166:
2162:
2141:
2134:
2131:
2127:
2123:
2120:
2117:
2113:
2109:
2106:
2103:
2098:
2095:
2092:
2089:
2085:
2082:
2079:
2076:
2073:
2069:
2045:
2040:
2037:
2034:
2029:
2026:
2023:
2019:
2011:
2008:
2004:
2000:
1997:
1993:
1989:
1984:
1981:
1978:
1975:
1970:
1967:
1964:
1960:
1955:
1947:
1944:
1940:
1936:
1933:
1929:
1925:
1918:
1915:
1911:
1907:
1903:
1898:
1894:
1891:
1864:
1861:
1858:
1855:
1850:
1847:
1844:
1840:
1836:
1831:
1828:
1825:
1822:
1817:
1814:
1811:
1807:
1803:
1798:
1795:
1792:
1787:
1784:
1780:
1755:
1750:
1747:
1744:
1741:
1736:
1733:
1730:
1726:
1718:
1715:
1711:
1707:
1704:
1700:
1696:
1691:
1688:
1685:
1682:
1677:
1674:
1671:
1667:
1659:
1656:
1652:
1648:
1644:
1640:
1637:
1616:
1612:
1604:
1600:
1596:
1591:
1587:
1582:
1578:
1575:
1571:
1565:
1562:
1559:
1554:
1551:
1547:
1543:
1540:
1536:
1530:
1527:
1524:
1520:
1516:
1511:
1508:
1505:
1502:
1497:
1494:
1491:
1487:
1460:
1456:
1452:
1447:
1443:
1438:
1432:
1429:
1426:
1421:
1418:
1414:
1410:
1407:
1403:
1397:
1394:
1391:
1387:
1383:
1378:
1375:
1372:
1369:
1364:
1361:
1358:
1354:
1329:
1324:
1320:
1314:
1310:
1304:
1301:
1298:
1294:
1290:
1285:
1282:
1279:
1276:
1273:
1270:
1267:
1264:
1261:
1257:
1253:
1250:
1247:
1244:
1239:
1236:
1232:
1211:
1191:
1166:
1163:
1160:
1157:
1154:
1151:
1147:
1141:
1138:
1135:
1131:
1127:
1124:
1093:
1089:
1083:
1079:
1073:
1070:
1067:
1063:
1059:
1054:
1051:
1048:
1045:
1042:
1038:
1034:
1031:
1028:
1025:
1022:
997:
994:
989:
986:
982:
954:
951:
947:
943:
940:
937:
933:
929:
926:
923:
919:
913:
909:
905:
900:
896:
891:
887:
884:
879:
876:
873:
869:
864:
860:
836:
833:
829:
825:
822:
819:
815:
811:
807:
801:
797:
793:
788:
784:
779:
775:
772:
767:
764:
761:
757:
752:
748:
728:
725:
721:
715:
711:
707:
702:
698:
693:
689:
686:
681:
678:
675:
671:
666:
662:
642:
639:
635:
629:
625:
621:
616:
612:
607:
603:
600:
595:
592:
589:
585:
580:
576:
567:
566:
565:
547:
543:
532:
528:
507:
504:
499:
496:
493:
489:
464:
444:
424:
421:
416:
413:
410:
406:
385:
382:
379:
376:
373:
370:
365:
362:
359:
355:
334:
331:
328:
298:Main article:
295:
292:
279:
276:
273:
253:
250:
247:
227:
224:
221:
201:
198:
195:
171:
168:
165:
145:
142:
139:
117:
113:
92:
72:
69:
13:
10:
9:
6:
4:
3:
2:
3937:
3926:
3923:
3921:
3918:
3916:
3913:
3911:
3908:
3907:
3905:
3894:
3890:
3886:
3882:
3878:
3874:
3870:
3866:
3862:
3858:
3853:
3849:
3845:
3841:
3837:
3833:
3829:
3825:
3821:
3816:
3812:
3808:
3804:
3800:
3796:
3792:
3788:
3784:
3779:
3776:
3772:
3768:
3764:
3760:
3756:
3752:
3748:
3744:
3740:
3736:
3731:
3730:
3722:
3718:
3714:
3710:
3706:
3702:
3698:
3694:
3690:
3683:
3680:
3675:
3671:
3666:
3661:
3657:
3653:
3649:
3645:
3641:
3637:
3633:
3626:
3623:
3618:
3614:
3610:
3606:
3602:
3598:
3594:
3590:
3586:
3579:
3576:
3571:
3567:
3563:
3559:
3555:
3551:
3547:
3543:
3539:
3535:
3531:
3524:
3521:
3516:
3512:
3508:
3504:
3500:
3496:
3492:
3488:
3484:
3480:
3476:
3469:
3466:
3459:
3455:
3452:
3450:
3447:
3445:
3442:
3440:
3437:
3435:
3432:
3431:
3427:
3425:
3423:
3419:
3415:
3411:
3410:KBD algorithm
3405:
3403:
3399:
3395:
3387:
3385:
3383:
3380:
3364:
3360:
3356:
3353:
3350:
3338:
3336:
3332:
3317:
3309:
3305:
3301:
3296:
3292:
3287:
3283:
3277:
3273:
3269:
3265:
3261:
3257:
3253:
3248:
3243:
3237:
3234:
3230:
3224:
3221:
3218:
3215:
3212:
3204:
3201:
3198:
3194:
3189:
3181:
3177:
3173:
3168:
3164:
3159:
3155:
3152:
3148:
3144:
3137:
3133:
3129:
3124:
3120:
3115:
3111:
3107:
3100:
3096:
3092:
3088:
3084:
3080:
3076:
3071:
3067:
3064:
3060:
3056:
3050:
3046:
3042:
3038:
3034:
3030:
3026:
3021:
3016:
3010:
3007:
3003:
2997:
2994:
2991:
2988:
2985:
2977:
2974:
2970:
2964:
2960:
2954:
2950:
2946:
2942:
2938:
2934:
2929:
2925:
2921:
2916:
2910:
2907:
2903:
2897:
2894:
2891:
2888:
2885:
2877:
2874:
2871:
2859:
2844:
2838:
2835:
2831:
2827:
2820:
2814:
2811:
2807:
2800:
2796:
2792:
2788:
2784:
2780:
2776:
2771:
2765:
2762:
2759:
2756:
2753:
2745:
2742:
2739:
2735:
2731:
2728:
2725:
2722:
2716:
2710:
2707:
2703:
2695:
2691:
2687:
2682:
2678:
2673:
2667:
2664:
2661:
2658:
2655:
2647:
2644:
2641:
2637:
2633:
2630:
2627:
2624:
2618:
2611:
2603:
2600:
2588:
2585:
2582:
2579:
2575:
2571:
2568:
2564:
2560:
2557:
2554:
2551:
2540:
2533:
2529:
2526:
2520:
2513:
2502:
2499:
2496:
2493:
2489:
2485:
2482:
2478:
2474:
2471:
2468:
2465:
2453:
2450:
2442:
2438:
2435:
2429:
2419:
2406:
2403:
2395:
2385:
2382:
2369:
2362:
2351:
2337:
2315:
2312:
2309:
2306:
2302:
2298:
2295:
2285:
2281:
2279:
2275:
2271:
2267:
2263:
2255:
2249:
2248:
2247:
2231:
2228:
2225:
2222:
2217:
2214:
2211:
2207:
2184:
2181:
2178:
2175:
2170:
2167:
2164:
2160:
2139:
2132:
2129:
2125:
2121:
2118:
2115:
2111:
2107:
2104:
2101:
2096:
2093:
2090:
2087:
2083:
2080:
2077:
2074:
2071:
2067:
2056:
2043:
2038:
2035:
2032:
2027:
2024:
2021:
2017:
2009:
2006:
2002:
1998:
1995:
1991:
1987:
1982:
1979:
1976:
1973:
1968:
1965:
1962:
1958:
1953:
1945:
1942:
1938:
1934:
1931:
1927:
1923:
1916:
1913:
1909:
1905:
1901:
1896:
1892:
1889:
1881:
1878:
1862:
1859:
1856:
1853:
1848:
1845:
1842:
1838:
1834:
1829:
1826:
1823:
1820:
1815:
1812:
1809:
1805:
1801:
1796:
1793:
1790:
1785:
1782:
1778:
1769:
1766:
1753:
1748:
1745:
1742:
1739:
1734:
1731:
1728:
1724:
1716:
1713:
1709:
1705:
1702:
1698:
1694:
1689:
1686:
1683:
1680:
1675:
1672:
1669:
1665:
1657:
1654:
1650:
1646:
1642:
1638:
1635:
1627:
1614:
1610:
1602:
1598:
1594:
1589:
1585:
1580:
1576:
1573:
1569:
1560:
1552:
1549:
1545:
1541:
1538:
1534:
1525:
1514:
1509:
1506:
1503:
1500:
1495:
1492:
1489:
1485:
1476:
1458:
1454:
1450:
1445:
1441:
1436:
1427:
1419:
1416:
1412:
1408:
1405:
1401:
1392:
1381:
1376:
1373:
1370:
1367:
1362:
1359:
1356:
1352:
1343:
1340:
1327:
1322:
1318:
1312:
1308:
1302:
1299:
1296:
1292:
1288:
1283:
1280:
1277:
1274:
1271:
1268:
1265:
1262:
1259:
1251:
1245:
1237:
1234:
1230:
1209:
1189:
1180:
1161:
1155:
1152:
1149:
1145:
1136:
1125:
1122:
1114:
1112:
1107:
1091:
1087:
1081:
1077:
1071:
1068:
1065:
1061:
1057:
1052:
1049:
1046:
1043:
1040:
1032:
1026:
1020:
1012:
1009:
995:
992:
987:
984:
980:
952:
949:
945:
941:
938:
935:
931:
927:
924:
921:
917:
911:
907:
903:
898:
894:
885:
882:
877:
874:
871:
867:
862:
858:
834:
831:
827:
823:
820:
817:
813:
809:
805:
799:
795:
791:
786:
782:
773:
770:
765:
762:
759:
755:
750:
746:
726:
723:
719:
713:
709:
705:
700:
696:
687:
684:
679:
676:
673:
669:
664:
660:
640:
637:
633:
627:
623:
619:
614:
610:
601:
598:
593:
590:
587:
583:
578:
574:
563:
560:(the bond is
545:
541:
530:
526:
505:
502:
497:
494:
491:
487:
478:
475:(the bond is
462:
442:
422:
419:
414:
411:
408:
404:
380:
377:
374:
368:
363:
360:
357:
353:
332:
329:
326:
318:
317:
316:
313:
311:
307:
301:
293:
291:
277:
274:
271:
251:
248:
245:
225:
222:
219:
199:
196:
193:
185:
169:
166:
163:
143:
140:
137:
115:
111:
90:
82:
78:
70:
68:
66:
62:
58:
54:
50:
45:
43:
39:
35:
31:
27:
23:
19:
3860:
3856:
3823:
3819:
3786:
3782:
3738:
3734:
3696:
3692:
3682:
3639:
3635:
3625:
3592:
3588:
3578:
3540:(1): 67–86.
3537:
3533:
3523:
3482:
3478:
3468:
3422:spin glasses
3406:
3391:
3342:
3333:
2860:
2352:
2286:
2282:
2262:Markov chain
2259:
2199:in favor of
2057:
1882:
1879:
1770:
1767:
1628:
1477:
1344:
1341:
1181:
1115:
1108:
1013:
1010:
971:
561:
476:
314:
303:
74:
46:
17:
15:
2256:Correctness
310:percolation
294:Description
81:Ising model
40:in 1987 at
30:criticality
3904:Categories
3665:2445/13250
3460:References
3339:Efficiency
71:Motivation
3877:0162-8828
3848:0378-4371
3811:0031-8914
3763:0031-9007
3570:189821827
3562:1572-9613
3499:0162-8828
3365:ν
3357:γ
3354:≥
3306:σ
3293:σ
3288:δ
3284:−
3270:σ
3254:σ
3249:δ
3209:∑
3202:−
3178:σ
3165:σ
3160:δ
3156:−
3134:σ
3121:σ
3116:δ
3112:−
3093:σ
3077:σ
3072:δ
3068:−
3057:−
3043:σ
3027:σ
3022:δ
2982:∑
2978:−
2961:σ
2951:σ
2947:−
2935:σ
2922:σ
2882:∑
2878:−
2869:Δ
2842:Δ
2839:β
2836:−
2793:σ
2777:σ
2772:δ
2750:∑
2746:β
2740:−
2732:
2726:⋅
2692:σ
2679:σ
2674:δ
2652:∑
2648:β
2642:−
2634:
2628:⋅
2601:σ
2541:σ
2514:σ
2451:σ
2420:σ
2414:→
2404:σ
2383:σ
2376:→
2370:σ
2313:β
2307:−
2122:β
2116:−
2108:−
1999:β
1996:−
1935:β
1932:−
1924:−
1906:β
1706:β
1703:−
1647:β
1599:σ
1586:σ
1581:δ
1577:−
1561:σ
1542:β
1539:−
1526:σ
1519:∑
1455:σ
1442:σ
1437:δ
1428:σ
1409:β
1406:−
1393:σ
1386:∑
1319:σ
1309:σ
1289:−
1256:∑
1246:σ
1162:σ
1153:β
1150:−
1137:σ
1130:∑
1088:σ
1078:σ
1058:−
1037:∑
1027:σ
942:β
936:−
928:−
908:σ
895:σ
824:β
818:−
796:σ
783:σ
710:σ
706:≠
697:σ
624:σ
620:≠
611:σ
542:σ
527:σ
369:∈
170:τ
167:≫
141:≃
91:τ
22:algorithm
3885:16119263
3771:10034599
3721:10043065
3674:10055635
3507:16119263
3428:See also
3412:for the
3278:′
3262:′
3101:′
3085:′
3051:′
3035:′
2943:′
2930:′
2801:′
2785:′
2604:′
2454:′
2407:′
2386:′
1109:and the
3828:Bibcode
3791:Bibcode
3783:Physica
3743:Bibcode
3701:Bibcode
3644:Bibcode
3617:9959355
3597:Bibcode
3542:Bibcode
2266:ergodic
3893:410716
3891:
3883:
3875:
3846:
3809:
3769:
3761:
3719:
3672:
3615:
3568:
3560:
3515:410716
3513:
3505:
3497:
2861:since
972:where
479:); if
477:closed
3889:S2CID
3566:S2CID
3511:S2CID
226:2.125
130:with
61:Potts
49:Ising
3881:PMID
3873:ISSN
3844:ISSN
3807:ISSN
3767:PMID
3759:ISSN
3717:PMID
3670:PMID
3613:PMID
3558:ISSN
3503:PMID
3495:ISSN
3225:>
3213:<
2998:>
2986:<
2898:>
2886:<
2766:>
2754:<
2668:>
2656:<
2084:>
2072:<
1284:>
1260:<
1202:and
1053:>
1041:<
993:>
562:open
455:and
252:0.75
200:0.35
36:and
24:for
16:The
3865:doi
3836:doi
3824:167
3799:doi
3751:doi
3709:doi
3660:hdl
3652:doi
3605:doi
3550:doi
3487:doi
2729:exp
2631:exp
1113:is
851:;
739:;
653:;
278:2.0
3906::
3887:.
3879:.
3871:.
3861:27
3859:.
3842:.
3834:.
3822:.
3805:.
3797:.
3787:57
3785:.
3765:.
3757:.
3749:.
3739:58
3737:.
3715:.
3707:.
3697:65
3695:.
3691:.
3668:.
3658:.
3650:.
3640:72
3638:.
3634:.
3611:.
3603:.
3593:38
3591:.
3587:.
3564:.
3556:.
3548:.
3538:97
3536:.
3532:.
3509:.
3501:.
3493:.
3483:27
3481:.
3477:.
3384:.
3331:.
1877:;
1475:;
1179:.
1106:,
969:;
44:.
3895:.
3867::
3850:.
3838::
3830::
3813:.
3801::
3793::
3773:.
3753::
3745::
3723:.
3711::
3703::
3676:.
3662::
3654::
3646::
3619:.
3607::
3599::
3572:.
3552::
3544::
3517:.
3489::
3361:/
3351:z
3318:)
3310:m
3302:,
3297:l
3274:m
3266:,
3258:l
3244:(
3238:m
3235:l
3231:J
3222:m
3219:,
3216:l
3205:2
3199:=
3195:]
3190:)
3182:m
3174:,
3169:l
3153:1
3149:(
3145:+
3138:m
3130:,
3125:l
3108:)
3097:m
3089:,
3081:l
3065:1
3061:(
3047:m
3039:,
3031:l
3017:[
3011:m
3008:l
3004:J
2995:m
2992:,
2989:l
2975:=
2971:)
2965:m
2955:l
2939:m
2926:l
2917:(
2911:m
2908:l
2904:J
2895:m
2892:,
2889:l
2875:=
2872:E
2845:E
2832:e
2828:=
2821:]
2815:m
2812:l
2808:J
2797:m
2789:,
2781:l
2763:m
2760:,
2757:l
2743:2
2736:[
2723:p
2717:]
2711:m
2708:l
2704:J
2696:m
2688:,
2683:l
2665:m
2662:,
2659:l
2645:2
2638:[
2625:p
2619:=
2612:)
2608:}
2597:{
2593:|
2589:.
2586:C
2583:.
2580:B
2576:(
2572:r
2569:P
2565:)
2561:.
2558:C
2555:.
2552:B
2548:|
2544:}
2538:{
2534:(
2530:r
2527:P
2521:)
2517:}
2511:{
2507:|
2503:.
2500:C
2497:.
2494:B
2490:(
2486:r
2483:P
2479:)
2475:.
2472:C
2469:.
2466:B
2462:|
2458:}
2447:{
2443:(
2439:r
2436:P
2430:=
2423:}
2417:{
2411:}
2400:{
2396:P
2390:}
2379:{
2373:}
2367:{
2363:P
2338:p
2316:J
2310:2
2303:e
2299:=
2296:q
2232:f
2229:f
2226:i
2223:d
2218:m
2215:,
2212:n
2208:Z
2185:e
2182:m
2179:a
2176:s
2171:m
2168:,
2165:n
2161:Z
2140:.
2133:m
2130:n
2126:J
2119:2
2112:e
2105:1
2102:=
2097:k
2094:n
2091:i
2088:l
2081:m
2078:,
2075:n
2068:P
2044:.
2039:d
2036:n
2033:i
2028:m
2025:,
2022:n
2018:Z
2010:m
2007:n
2003:J
1992:e
1988:+
1983:e
1980:m
1977:a
1974:s
1969:m
1966:,
1963:n
1959:Z
1954:)
1946:m
1943:n
1939:J
1928:e
1917:m
1914:n
1910:J
1902:e
1897:(
1893:=
1890:Z
1863:f
1860:f
1857:i
1854:d
1849:m
1846:,
1843:n
1839:Z
1835:+
1830:e
1827:m
1824:a
1821:s
1816:m
1813:,
1810:n
1806:Z
1802:=
1797:d
1794:n
1791:i
1786:m
1783:n
1779:Z
1754:.
1749:f
1746:f
1743:i
1740:d
1735:m
1732:,
1729:n
1725:Z
1717:m
1714:n
1710:J
1699:e
1695:+
1690:e
1687:m
1684:a
1681:s
1676:m
1673:,
1670:n
1666:Z
1658:m
1655:n
1651:J
1643:e
1639:=
1636:Z
1615:.
1611:)
1603:m
1595:,
1590:n
1574:1
1570:(
1564:]
1558:[
1553:m
1550:n
1546:H
1535:e
1529:}
1523:{
1515:=
1510:f
1507:f
1504:i
1501:d
1496:m
1493:,
1490:n
1486:Z
1459:m
1451:,
1446:n
1431:]
1425:[
1420:m
1417:n
1413:H
1402:e
1396:}
1390:{
1382:=
1377:e
1374:m
1371:a
1368:s
1363:m
1360:,
1357:n
1353:Z
1328:.
1323:j
1313:i
1303:j
1300:,
1297:i
1293:J
1281:m
1278:,
1275:n
1269:j
1266:,
1263:i
1252:=
1249:]
1243:[
1238:m
1235:n
1231:H
1210:m
1190:n
1165:]
1159:[
1156:H
1146:e
1140:}
1134:{
1126:=
1123:Z
1092:j
1082:i
1072:j
1069:,
1066:i
1062:J
1050:j
1047:,
1044:i
1033:=
1030:]
1024:[
1021:H
996:0
988:m
985:n
981:J
953:m
950:n
946:J
939:2
932:e
925:1
922:=
918:]
912:m
904:=
899:n
890:|
886:1
883:=
878:m
875:,
872:n
868:b
863:[
859:P
835:m
832:n
828:J
821:2
814:e
810:=
806:]
800:m
792:=
787:n
778:|
774:0
771:=
766:m
763:,
760:n
756:b
751:[
747:P
727:0
724:=
720:]
714:m
701:n
692:|
688:1
685:=
680:m
677:,
674:n
670:b
665:[
661:P
641:1
638:=
634:]
628:m
615:n
606:|
602:0
599:=
594:m
591:,
588:n
584:b
579:[
575:P
546:m
531:n
506:1
503:=
498:m
495:,
492:n
488:b
463:m
443:n
423:0
420:=
415:m
412:,
409:n
405:b
384:}
381:1
378:,
375:0
372:{
364:m
361:,
358:n
354:b
333:m
330:,
327:n
275:=
272:z
249:=
246:z
223:=
220:z
197:=
194:z
164:t
144:2
138:z
116:z
112:L
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.