Алгоритм Свендсена–Ванга

Алгоритм Свендсена–Вана — первый нелокальный или кластерный алгоритм для моделирования Монте-Карло для больших систем вблизи критичности . Он был представлен Робертом Свендсеном и Цзянь-Шэном Ваном в 1987 году в Университете Карнеги-Меллона .

Первоначальный алгоритм был разработан для моделей Изинга и Поттса, а затем был обобщен и на другие системы, такие как модель XY алгоритмом Вольфа и частицы жидкостей. Ключевым компонентом была модель случайного кластера , представление модели Изинга или Поттса через модели перколяции соединительных связей, предложенные Фортуином и Кастелейном. Он был обобщен Барбу и Чжу ^[1] на произвольные вероятности выборки, рассматривая его как алгоритм Метрополиса–Гастингса и вычисляя вероятность принятия предложенного хода Монте-Карло.

Мотивация

Проблема критического замедления, влияющего на локальные процессы, имеет фундаментальное значение при изучении фазовых переходов второго рода (например, ферромагнитного перехода в модели Изинга ), поскольку увеличение размера системы с целью уменьшения эффектов конечного размера имеет тот недостаток, что для достижения теплового равновесия требуется гораздо большее количество перемещений. Действительно, время корреляции обычно увеличивается как или больше; поскольку, если быть точным, время моделирования должно быть , это является основным ограничением размера систем, которые можно изучать с помощью локальных алгоритмов . Алгоритм SW был первым, кто выдал необычно малые значения для динамических критических показателей: для 2D-модели Изинга ( для стандартных симуляций); для 3D-модели Изинга, в отличие от стандартных симуляций. ${\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}$

Описание

Алгоритм нелокален в том смысле, что один проход обновляет набор спиновых переменных на основе представления Фортуина–Кастелейна . Обновление выполняется на «кластере» спиновых переменных, связанных открытыми переменными связи, которые генерируются посредством процесса перколяции на основе состояний взаимодействия спинов.

Рассмотрим типичную ферромагнитную модель Изинга, в которой взаимодействуют только ближайшие соседи.

• Начиная с заданной конфигурации спинов, мы связываем с каждой парой ближайших соседей на сайтах случайную величину , которая интерпретируется следующим образом: если то нет связи между сайтами и (связь закрыта ); если то есть связь, соединяющая спины (связь открыта ). Эти значения присваиваются в соответствии со следующим (условным) распределением вероятностей: ${\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}}}$

где - сила ферромагнитной связи. ${\displaystyle J_{nm}>0}$

Это распределение вероятностей было получено следующим образом: гамильтониан модели Изинга равен

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

и функция распределения равна

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

Рассмотрим взаимодействие между парой выбранных сайтов и и исключим его из общего гамильтониана, определив ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle H_{nm}[\sigma ]=\sum \limits _{<i,j>\neq <n,m>}-J_{i,j}\sigma _{i}\sigma _{j}.}$

Определим также ограниченные суммы:

${\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}.}$

Введите количество

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

функцию распределения можно переписать как

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

Поскольку первый член содержит ограничение на значения спина, тогда как во втором члене ограничений нет, весовые коэффициенты (правильно нормированные) можно интерпретировать как вероятности образования/несоздания связи между узлами: Процесс можно легко адаптировать к антиферромагнитным спиновым системам, поскольку достаточно исключить в пользу (как предполагает изменение знака в константе взаимодействия). ${\displaystyle P_{<n,m>\;link}=1-e^{-2\beta J_{nm}}.}$ ${\displaystyle Z_{n,m}^{same}}$ ${\displaystyle Z_{n,m}^{diff}}$

• После назначения переменных связей мы идентифицируем кластеры с одинаковым спином, образованные связанными сайтами, и делаем инверсию всех переменных в кластере с вероятностью 1/2. На следующем временном шаге у нас есть новая начальная конфигурация Изинга, которая создаст новую кластеризацию и новый коллективный спин-флип.

Корректность

Можно показать, что этот алгоритм приводит к равновесным конфигурациям. Чтобы показать это, мы интерпретируем алгоритм как цепь Маркова и показываем, что цепь является как эргодической (при использовании вместе с другими алгоритмами), так и удовлетворяет детальному балансу , так что равновесное распределение Больцмана равно стационарному распределению цепи.

Эргодичность означает, что возможен переход из любого начального состояния в любое конечное состояние с конечным числом обновлений. Было показано, что алгоритм SW в общем случае не является эргодическим (в термодинамическом пределе). ^[2] Таким образом, на практике алгоритм SW обычно используется в сочетании с алгоритмами одиночного переворота спина, такими как алгоритм Метрополиса–Гастингса, для достижения эргодичности.

Алгоритм SW, однако, удовлетворяет детальному балансу. Чтобы показать это, отметим, что каждый переход между двумя спиновыми состояниями Изинга должен проходить через некоторую конфигурацию связей в перколяционном представлении. Давайте зафиксируем конкретную конфигурацию связей: при сравнении вероятностей, связанных с ней, имеет значение количество факторов для каждой отсутствующей связи между соседними спинами с одинаковым значением; вероятность перехода к определенной конфигурации Изинга, совместимой с данной конфигурацией связей, является однородной (скажем, ). Таким образом, отношение вероятностей перехода из одного состояния в другое равно ${\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}}$

с . ${\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)}$

Это справедливо для каждой конфигурации связей, через которую может пройти система в ходе своей эволюции, поэтому детальный баланс выполняется для общей вероятности перехода. Это доказывает, что алгоритм верен.

Эффективность

Хотя аналитически из оригинальной статьи это не ясно, причина, по которой все значения z, полученные с помощью алгоритма SW, намного ниже точной нижней границы для алгоритмов с одним спином-переворотом ( ), заключается в том, что расхождение длины корреляции строго связано с образованием кластеров перколяции, которые переворачиваются вместе. Таким образом, время релаксации значительно сокращается. Другой способ рассмотреть это — через соответствие между статистикой спина и статистикой кластера в представлении Эдвардса-Сокала . ^[3] Некоторые математически строгие результаты по времени смешивания этого процесса были получены Го и Джеррумом [1]. ${\displaystyle z\geq \gamma /\nu }$

Обобщения

Алгоритм неэффективен при моделировании фрустрированных систем , поскольку длина корреляции кластеров больше, чем длина корреляции спиновой модели при наличии фрустрированных взаимодействий. ^[4] В настоящее время существует два основных подхода к решению этой проблемы, так что эффективность кластерных алгоритмов распространяется на фрустрированные системы.

Первый подход заключается в расширении правил формирования связей на более нелокальные ячейки, а второй подход заключается в создании кластеров на основе более релевантных параметров порядка. В первом случае у нас есть алгоритм KBD для полностью фрустрированной модели Изинга , где решение об открытии связей принимается на каждой плакетке, расположенной в шахматном порядке на квадратной решетке. ^[5] Во втором случае у нас есть перемещение кластера реплик для низкоразмерных спиновых стекол , где кластеры генерируются на основе спиновых перекрытий, что, как полагают, является релевантным параметром порядка.

Смотрите также

• Модель случайного кластера
• Метод Монте-Карло
• Алгоритм Вольфа
• http://www.hpjava.org/theses/shko/thesis_paper/node69.html
• http://www-fcs.acs.i.kyoto-u.ac.jp/~harada/monte-en.html

Ссылки

1. Барбу, Адриан; Чжу, Сонг-Чун (август 2005 г.). «Обобщение Свендсена-Вана для выборки произвольных апостериорных вероятностей». Труды IEEE по анализу шаблонов и машинному интеллекту . 27 (8): 1239–1253. doi :10.1109/TPAMI.2005.161. ISSN  0162-8828. PMID  16119263. S2CID  410716.
2. Гор, Вивек К.; Джеррум, Марк Р. (1999-10-01). «Процесс Свендсена–Вана не всегда быстро смешивается». Журнал статистической физики . 97 (1): 67–86. Bibcode :1999JSP....97...67G. doi :10.1023/A:1004610900745. ISSN  1572-9613. S2CID  189821827.
3. Эдвардс, Роберт Г.; Сокал, Алан Д. (1988-09-15). «Обобщение представления Фортуина-Кастелейна-Свендсена-Ванга и алгоритм Монте-Карло». 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. (1994-03-07). «Критические кластеры и эффективная динамика для моделей фрустрированного спина». Physical Review Letters . 72 (10): 1541–1544. Bibcode :1994PhRvL..72.1541C. doi :10.1103/PhysRevLett.72.1541. hdl : 2445/13250 . PMID  10055635.
5. Кандел, Дэниел; Бен-Ав, Радел; Домани, Эйтан (1990-08-20). «Динамика кластера для полностью фрустрированных систем». Physical Review Letters . 65 (8): 941–944. Bibcode :1990PhRvL..65..941K. doi :10.1103/PhysRevLett.65.941. PMID  10043065.

• Свендсен, Роберт Х.; Ван, Цзянь-Шэн (1987-01-12). «Неуниверсальная критическая динамика в моделировании Монте-Карло». Physical Review Letters . 58 (2). Американское физическое общество (APS): 86–88. Bibcode : 1987PhRvL..58...86S. doi : 10.1103/physrevlett.58.86. ISSN  0031-9007. PMID  10034599.
• Kasteleyn PW и Fortuin (1969) J. Phys. Soc. Jpn. Suppl. 26s:11
• Fortuin, CM; Kasteleyn, PW (1972). «О модели случайных кластеров». Physica . 57 (4). Elsevier BV: 536–564. Bibcode :1972Phy....57..536F. doi :10.1016/0031-8914(72)90045-6. ISSN  0031-8914.
• Ван, Цзянь-Шэн; Свендсен, Роберт Х. (1990). «Кластерные алгоритмы Монте-Карло». Physica A: Статистическая механика и ее приложения . 167 (3). Elsevier BV: 565–579. Bibcode : 1990PhyA..167..565W. doi : 10.1016/0378-4371(90)90275-w. ISSN  0378-4371.
• Барбу, А. (2005). «Обобщение Свендсена-Ванга для выборки произвольных апостериорных вероятностей». Труды IEEE по анализу шаблонов и машинному интеллекту . 27 (8). Институт инженеров по электротехнике и электронике (IEEE): 1239–1253. doi :10.1109/tpami.2005.161. ISSN  0162-8828. PMID  16119263. S2CID  410716.