Algoritmo de Swendsen-Wang

El algoritmo de Swendsen - Wang es el primer algoritmo no local o de clúster para la simulación de Monte Carlo de sistemas grandes cercanos a la criticidad . Fue presentado por Robert Swendsen y Jian-Sheng Wang en 1987 en la Universidad Carnegie Mellon .

El algoritmo original fue diseñado para los modelos de Ising y Potts, y posteriormente se generalizó a otros sistemas, como el modelo XY mediante el algoritmo de Wolff y partículas de fluidos. El ingrediente clave fue el modelo de clúster aleatorio , una representación del modelo de Ising o Potts a través de modelos de percolación de enlaces de conexión, debido a Fortuin y Kasteleyn. Barbu y Zhu ^{[ 1 ]} lo generalizaron a probabilidades de muestreo arbitrarias al considerarlo como un algoritmo de Metropolis-Hastings y calcular la probabilidad de aceptación del movimiento de Monte Carlo propuesto.

El problema de la ralentización crítica que afecta a los procesos locales es de fundamental importancia en el estudio de las transiciones de fase de segundo orden (como la transición ferromagnética en el modelo de Ising ), ya que aumentar el tamaño del sistema para reducir los efectos de tamaño finito tiene la desventaja de requerir un número mucho mayor de movimientos para alcanzar el equilibrio térmico . De hecho, el tiempo de correlación${\displaystyle \tau }$suele aumentar a medida que${\displaystyle L^{z}}$con${\displaystyle z\simeq 2}$o mayor; puesto que, para ser preciso, el tiempo de simulación debe ser${\displaystyle t\gg \tau }$Esto representa una limitación importante en el tamaño de los sistemas que pueden estudiarse mediante algoritmos locales . El algoritmo SW fue el primero en producir valores inusualmente pequeños para los exponentes críticos dinámicos:${\displaystyle z=0.35}$para el modelo de Ising 2D (${\displaystyle z=2.125}$para simulaciones estándar);${\displaystyle z=0.75}$para el modelo de Ising 3D, a diferencia de${\displaystyle z=2.0}$para simulaciones estándar.

El algoritmo es no local en el sentido de que un solo barrido actualiza un conjunto de variables de espín basadas en la representación de Fortuin-Kasteleyn . La actualización se realiza sobre un "grupo" de variables de espín conectadas por variables de enlace abierto que se generan mediante un proceso de percolación , basado en los estados de interacción de los espines.

Consideremos un modelo de Ising ferromagnético típico con interacción únicamente entre vecinos próximos.

• Partiendo de una configuración dada de espines, asociamos a cada par de vecinos más cercanos en sitios${\displaystyle n,m}$una variable aleatoria${\displaystyle b_{n,m}\in \lbrace 0,1\rbrace }$lo cual se interpreta de la siguiente manera: si${\displaystyle b_{n,m}=0}$entonces no hay ningún vínculo entre los sitios${\displaystyle n}$y${\displaystyle m}$(el bono está cerrado ); si${\displaystyle b_{n,m}=1}$entonces hay un vínculo que conecta los giros${\displaystyle \sigma _{n}{\text{ y }}\sigma _{m}}$(el bono está abierto ). Estos valores se asignan de acuerdo con la siguiente distribución de probabilidad (condicional) :

${\displaystyle P\left[b_{n,m}=0|\sigma _{n}\neq \sigma _{m}\right]=1}$; ${\displaystyle P\left[b_{n,m}=1|\sigma _{n}\neq \sigma _{m}\right]=0}$; ${\displaystyle P\left[b_{n,m}=0|\sigma _{n}=\sigma _{m}\right]=e^{-2\beta J_{nm}}}$; ${\displaystyle P\left[b_{n,m}=1|\sigma _{n}=\sigma _{m}\right]=1-e^{-2\beta J_{nm}}}$;

dónde${\displaystyle J_{nm}>0}$es la fuerza de acoplamiento ferromagnético.

Esta distribución de probabilidad se ha derivado de la siguiente manera: el hamiltoniano del modelo de Ising es

${\displaystyle H[\sigma ]=\sum \limits _{<i,j>}-J_{i,j}\sigma _{i}\sigma _{j}}$,

y la función de partición es

${\displaystyle Z=\sum \limits _{\lbrace \sigma \rbrace }e^{-\beta H[\sigma ]}}$.

Consideremos la interacción entre un par de sitios seleccionados.${\displaystyle n}$y${\displaystyle m}$y eliminarlo del hamiltoniano total, definiendo ${\displaystyle H_{nm}[\sigma ]=\sum \limits _{<i,j>\neq <n,m>}-J_{i,j}\sigma _{i}\sigma _{j}.}$

Defina también las sumas restringidas:

${\displaystyle Z_{n,m}^{same}=\sum \limits _{\lbrace \sigma \rbrace }e^{-\beta H_{nm}[\sigma ]}\delta _{\sigma _{n},\sigma _{m}}}$;

${\displaystyle Z_{n,m}^{diff}=\sum \limits _{\lbrace \sigma \rbrace }e^{-\beta H_{nm}[\sigma ]}\left(1-\delta _{\sigma _{n},\sigma _{m}}\right).}$

${\displaystyle Z=e^{\beta J_{nm}}Z_{n,m}^{igual}+e^{-\beta J_{nm}}Z_{n,m}^{diferente}.}$

Introducir la cantidad

${\displaystyle Z_{nm}^{ind}=Z_{n,m}^{igual}+Z_{n,m}^{diferente}}$;

La función de partición se puede reescribir como

${\displaystyle Z=\left(e^{\beta J_{nm}}-e^{-\beta J_{nm}}\right)Z_{n,m}^{igual}+e^{-\beta J_{nm}}Z_{n,m}^{ind}.}$

Dado que el primer término contiene una restricción en los valores de espín, mientras que no hay ninguna restricción en el segundo término, los factores de ponderación (debidamente normalizados) pueden interpretarse como probabilidades de formar o no formar un enlace entre los sitios:${\displaystyle P_{<n,m>\;link}=1-e^{-2\beta J_{nm}}.}$ El proceso se puede adaptar fácilmente a sistemas de espín antiferromagnéticos , ya que basta con eliminar${\displaystyle Z_{n,m}^{same}}$a favor de${\displaystyle Z_{n,m}^{diff}}$(como sugiere el cambio de signo en la constante de interacción).

• Tras asignar las variables de enlace, identificamos los clústeres de espín idéntico formados por sitios conectados y realizamos una inversión de todas las variables del clúster con probabilidad 1/2. En el siguiente paso temporal, obtenemos una nueva configuración de Ising inicial, que generará una nueva agrupación y un nuevo cambio de espín colectivo.

Se puede demostrar que este algoritmo conduce a configuraciones de equilibrio. Para ello, interpretamos el algoritmo como una cadena de Markov y mostramos que la cadena es ergódica (cuando se utiliza junto con otros algoritmos) y satisface el equilibrio detallado , de modo que la distribución de Boltzmann de equilibrio es igual a la distribución estacionaria de la cadena.

La ergodicidad implica que es posible transitar de cualquier estado inicial a cualquier estado final con un número finito de actualizaciones. Se ha demostrado que el algoritmo SW no es ergódico en general (en el límite termodinámico ). ^{[ 2 ]} Por lo tanto, en la práctica, el algoritmo SW se suele utilizar junto con algoritmos de inversión de espín simple, como el algoritmo de Metropolis-Hastings, para lograr la ergodicidad.

Sin embargo, el algoritmo SW satisface el equilibrio detallado. Para demostrarlo, observamos que cada transición entre dos estados de espín de Ising debe pasar por alguna configuración de enlace en la representación de percolación. Fijemos una configuración de enlace particular: lo que importa al comparar las probabilidades relacionadas con ella es el número de factores.${\displaystyle q=e^{-2\beta J}}$para cada enlace faltante entre espines vecinos con el mismo valor; la probabilidad de ir a una determinada configuración de Ising compatible con una configuración de enlace dada es uniforme (por ejemplo,${\displaystyle p}$). Por lo tanto, la razón de las probabilidades de transición de pasar de un estado a otro es

${\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[-2\beta \sum \limits _{<l,m>}\delta _{\sigma _{l},\sigma _{m}}J_{lm}\right]}{p\cdot \exp \left[-2\beta \sum \limits _{<l,m>}\delta _{\sigma '_{l},\sigma '_{m}}J_{lm}\right]}}=e^{-\beta \Delta E}}$

desde${\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[\delta _{\sigma '_{l},\sigma '_{m}}-\left(1-\delta _{\sigma '_{l},\sigma '_{m}}\right)-\delta _{\sigma _{l},\sigma _{m}}+\left(1-\delta _{\sigma _{l},\sigma _{m}}\right)\right]=-2\sum \limits _{<l,m>}J_{lm}\left(\delta _{\sigma '_{l},\sigma '_{m}}-\delta _{\sigma _{l},\sigma _{m}}\right)}$.

Esto es válido para cada configuración de enlace por la que el sistema puede pasar durante su evolución, por lo que se cumple el equilibrio detallado para la probabilidad total de transición. Esto demuestra que el algoritmo es correcto.

Aunque no queda analíticamente claro en el artículo original, la razón por la que todos los valores de z obtenidos con el algoritmo SW son mucho menores que el límite inferior exacto para los algoritmos de inversión de espín único (${\displaystyle z\geq \gamma /\nu }$) es que la divergencia de la longitud de correlación está estrictamente relacionada con la formación de cúmulos de percolación, que se voltean juntos. De esta manera, el tiempo de relajación se reduce significativamente. Otra forma de ver esto es a través de la correspondencia entre las estadísticas de espín y las estadísticas de cúmulos en la representación de Edwards-Sokal . ^{[ 3 ]} Guo y Jerrum han obtenido algunos resultados matemáticamente rigurosos sobre el tiempo de mezcla de este proceso..

El algoritmo no es eficiente en la simulación de sistemas frustrados , porque la longitud de correlación de los clústeres es mayor que la longitud de correlación del modelo de espín en presencia de interacciones frustradas. ^{[ 4 ]} Actualmente, existen dos enfoques principales para abordar este problema, de modo que la eficiencia de los algoritmos de clúster se extiende a sistemas frustrados.

El primer enfoque consiste en extender las reglas de formación de enlaces a celdas más no locales, y el segundo en generar clústeres basados ​​en parámetros de orden más relevantes. En el primer caso, tenemos el algoritmo KBD para el modelo de Ising totalmente frustrado , donde la decisión de abrir enlaces se toma en cada plaqueta, dispuesta en un patrón de tablero de ajedrez en la red cuadrada . ^{[ 5 ]} En el segundo caso, tenemos el movimiento de clústeres de réplica para vidrios de espín de baja dimensión , donde los clústeres se generan en función de las superposiciones de espín, que se cree que es el parámetro de orden relevante.

• modelo de clúster aleatorio
• método de Monte Carlo
• Algoritmo de Wolff
• http://www.hpjava.org/theses/shko/thesis_paper/node69.html
• http://www-fcs.acs.i.kyoto-u.ac.jp/~harada/monte-en.html

• Swendsen, Robert H.; Wang, Jian-Sheng (1987-01-12). "Dinámica crítica no universal en simulaciones de Monte Carlo". Physical Review Letters . 58 (2). American Physical Society (APS): 86– 88. Bibcode : 1987PhRvL..58...86S . doi : 10.1103/physrevlett.58.86 . ISSN 0031-9007 . PMID 10034599 .  
• Kasteleyn PW y Fortuin (1969) J. Phys. Soc. Jpn. Suppl. 26s:11
• Fortuin, CM; Kasteleyn, PW (1972). "Sobre el modelo de clúster aleatorio". Physica . 57 (4). Elsevier BV: 536– 564. Bibcode : 1972Phy....57..536F . doi : 10.1016/0031-8914(72)90045-6 . ISSN 0031-8914 . 
• Wang, Jian-Sheng; Swendsen, Robert H. (1990). "Algoritmos de Monte Carlo de clúster". Physica A: Mecánica estadística y sus aplicaciones . 167 (3). Elsevier BV: 565– 579. Bibcode : 1990PhyA..167..565W . doi : 10.1016/0378-4371(90)90275-w . ISSN 0378-4371 . 
• Barbu, A. (2005). "Generalización de Swendsen-Wang al muestreo de probabilidades posteriores arbitrarias". IEEE Transactions on Pattern Analysis and Machine Intelligence . 27 (8). Institute of Electrical and Electronics Engineers (IEEE): 1239– 1253. Bibcode : 2005ITPAM..27.1239B . doi : 10.1109 / tpami.2005.161 . ISSN 0162-8828 . PMID 16119263. S2CID 410716 .