Algoritmo de Swendsen-Wang

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

El algoritmo original fue diseñado para los modelos de Ising y Potts, y luego fue generalizado a otros sistemas también, como el modelo XY por el algoritmo de Wolff y partículas de fluidos. El ingrediente clave fue el modelo de conglomerados aleatorios , 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. Ha sido generalizado por Barbu y Zhu ^[1] a probabilidades de muestreo arbitrarias al verlo como un algoritmo de Metropolis-Hastings y calcular la probabilidad de aceptación del movimiento de Monte Carlo propuesto.

Motivación

El problema de la desaceleración crítica que afecta a los procesos locales es de importancia fundamental 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 generalmente aumenta como con o mayor; dado que, para ser precisos, el tiempo de simulación debe ser , esta es una limitación importante en el tamaño de los sistemas que se pueden estudiar a través de algoritmos locales . El algoritmo SW fue el primero en producir valores inusualmente pequeños para los exponentes críticos dinámicos: para el modelo de Ising 2D ( para simulaciones estándar); para el modelo de Ising 3D, a diferencia de para simulaciones estándar. ${\displaystyle \tau }$ ${\displaystyle L^{z}}$ ${\displaystyle z\simeq 2}$ ${\displaystyle t\gg \tau }$ ${\displaystyle z=0.35}$ ${\displaystyle z=2.125}$ ${\displaystyle z=0.75}$ ${\displaystyle z=2.0}$

Descripción

El algoritmo no es local en el sentido de que un único barrido actualiza una colección de variables de espín basadas en la representación de Fortuin-Kasteleyn . La actualización se realiza en un "cúmulo" de variables de espín conectadas por variables de enlace abierto que se generan a través de 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 solo interacción con el vecino más cercano.

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

  ${\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 está la fuerza de acoplamiento ferromagnético? ${\displaystyle J_{nm}>0}$

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 ]}}$.

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

Definir 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}^{same}+e^{-\beta J_{nm}}Z_{n,m}^{diff}.}$

Introducir la cantidad

${\displaystyle Z_{nm}^{ind}=Z_{n,m}^{same}+Z_{n,m}^{diff}}$;

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}^{same}+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 restricción en el segundo término, los factores de ponderación (normalizados adecuadamente) se pueden interpretar como probabilidades de formar/no formar un enlace entre los sitios: El proceso se puede adaptar fácilmente a los sistemas de espín antiferromagnéticos, ya que es suficiente eliminar a favor de (como lo sugiere el cambio de signo en la constante de interacción). ${\displaystyle P_{<n,m>\;link}=1-e^{-2\beta J_{nm}}.}$ ${\displaystyle Z_{n,m}^{same}}$ ${\displaystyle Z_{n,m}^{diff}}$

• Después de asignar las variables de enlace, identificamos los cúmulos de espín idénticos formados por sitios conectados y realizamos una inversión de todas las variables del cúmulo con probabilidad 1/2. En el siguiente paso de tiempo tenemos una nueva configuración de Ising inicial, que producirá un nuevo agrupamiento y un nuevo cambio de espín colectivo.

Exactitud

Se puede demostrar que este algoritmo conduce a configuraciones de equilibrio. Para demostrarlo, interpretamos el algoritmo como una cadena de Markov y demostramos 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 significa que es posible pasar 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 suele utilizarse junto con algoritmos de inversión de espín único, como el algoritmo 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 para cada enlace faltante entre espines vecinos con el mismo valor; la probabilidad de pasar a una cierta configuración de Ising compatible con una configuración de enlace dada es uniforme (digamos ). Por lo tanto, la relación de las probabilidades de transición de pasar de un estado a otro es ${\displaystyle q=e^{-2\beta J}}$ ${\displaystyle p}$

${\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 cualquier configuración de enlace por la que pueda pasar el sistema durante su evolución, por lo que se satisface el balance detallado para la probabilidad total de transición. Esto demuestra que el algoritmo es correcto.

Eficiencia

Aunque no está analíticamente claro a partir del artículo original, la razón por la que todos los valores de z obtenidos con el algoritmo SW son mucho más bajos que el límite inferior exacto para los algoritmos de inversión de espín único ( ) 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 invierten 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 [1]. ${\displaystyle z\geq \gamma /\nu }$

Generalizaciones

El algoritmo no es eficiente para simular 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ústeres se extienda a los sistemas frustrados.

El primer enfoque es extender las reglas de formación de enlaces a más células no locales, y el segundo enfoque es generar grupos basados ​​en parámetros de orden más relevantes. En el primer caso, tenemos el algoritmo KBD para el modelo de Ising completamente 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 grupo de réplicas para vidrios de espín de baja dimensión , donde los grupos se generan en función de superposiciones de espín, que se cree que es el parámetro de orden relevante.

Véase también

• Modelo de conglomerados aleatorios
• 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

Referencias

1. Barbu, Adrian; Zhu, Song-Chun (agosto de 2005). "Generalización de Swendsen-Wang para muestrear probabilidades posteriores arbitrarias". IEEE Transactions on Pattern Analysis and Machine Intelligence . 27 (8): 1239–1253. doi :10.1109/TPAMI.2005.161. ISSN  0162-8828. PMID  16119263. S2CID  410716.
2. Gore, Vivek K.; Jerrum, Mark R. (1999-10-01). "El proceso Swendsen-Wang no siempre se mezcla rápidamente". Journal of Statistical Physics . 97 (1): 67–86. Bibcode :1999JSP....97...67G. doi :10.1023/A:1004610900745. ISSN  1572-9613. S2CID  189821827.
3. Edwards, Robert G.; Sokal, Alan D. (15 de septiembre de 1988). "Generalización de la representación de Fortuin-Kasteleyn-Swendsen-Wang y el algoritmo de Monte Carlo". Physical Review D . 38 (6): 2009–2012. Bibcode :1988PhRvD..38.2009E. doi :10.1103/PhysRevD.38.2009. PMID  9959355.
4. Cataudella, V.; Franzese, G.; Nicodemi, M.; Scala, A.; Coniglio, A. (7 de marzo de 1994). "Clústeres críticos y dinámica eficiente para modelos de espín frustrado". Physical Review Letters . 72 (10): 1541–1544. Bibcode :1994PhRvL..72.1541C. doi :10.1103/PhysRevLett.72.1541. hdl : 2445/13250 . PMID  10055635.
5. Kandel, Daniel; Ben-Av, Radel; Domany, Eytan (20 de agosto de 1990). "Dinámica de clústeres para sistemas completamente frustrados". Physical Review Letters . 65 (8): 941–944. Bibcode :1990PhRvL..65..941K. doi :10.1103/PhysRevLett.65.941. PMID  10043065.

• Swendsen, Robert H.; Wang, Jian-Sheng (12 de enero de 1987). "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 agrupamiento 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 en 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 para el muestreo de probabilidades posteriores arbitrarias". IEEE Transactions on Pattern Analysis and Machine Intelligence . 27 (8). Instituto de Ingenieros Eléctricos y Electrónicos (IEEE): 1239–1253. doi :10.1109/tpami.2005.161. ISSN  0162-8828. PMID  16119263. S2CID  410716.