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

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

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

Мотивация

Проблема критического замедления, влияющего на локальные процессы, имеет фундаментальное значение при изучении фазовых переходов второго рода (например, ферромагнитного перехода в модели Изинга ), поскольку увеличение размера системы с целью уменьшения эффектов конечного размера имеет большое значение. недостатком является необходимость гораздо большего количества ходов для достижения теплового равновесия. Действительно, время корреляции $\tau$ обычно увеличивается по мере $L^{z}$ с $z\simeq 2$ или больше; поскольку, чтобы быть точным, время моделирования должно быть $t\gg \tau$ Это главное ограничение размера систем, которые можно изучать с помощью локальных алгоритмов . Алгоритм SW был первым, кто выдал необычно малые значения динамических критических показателей: $z=0.35$ для 2D-модели Изинга ( $z=2.125$ для стандартного моделирования); $z=0.75$ для 3D-модели Изинга, в отличие от $z=2.0$ для стандартных симуляций.

Описание

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

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

Каждой паре ближайших соседей на узлах, исходя из заданной конфигурации спинов, сопоставляем $n,m$ случайная величина $b_{n,m}\in \lbrace 0,1\rbrace$ что интерпретируется следующим образом: если $b_{n,m}=0$ тогда нет связи между сайтами $n$ и $m$ (облигация закрыта ); если $b_{n,m}=1$ тогда есть связь, соединяющая спины $\sigma _{n}{\text{ and }}\sigma _{m}$ (облигация открыта ). Эти значения присваиваются в соответствии со следующим (условным) распределением вероятностей:

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

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

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

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

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

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

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

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

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

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

$Z=e^{\beta J_{nm}}Z_{n,m}^{same}+e^{-\beta J_{nm}}Z_{n,m}^{diff}.$

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

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

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

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

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

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

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

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

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

Алгоритм ПО, однако, удовлетворяет детальному балансу. Чтобы показать это, заметим, что каждый переход между двумя спиновыми состояниями Изинга должен проходить через некоторую конфигурацию связей в перколяционном представлении. Зафиксируем конкретную конфигурацию облигации: при сравнении связанных с ней вероятностей важно количество факторов. $q=e^{-2\beta J}$ за каждую недостающую связь между соседними спинами одинакового значения; вероятность перехода к определенной конфигурации Изинга, совместимой с данной конфигурацией связей, одинакова (скажем, $p$ ). Тогда отношение переходных вероятностей перехода из одного состояния в другое равно

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

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

Обобщения

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

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

См. также

Ссылки

^ Барбу, Адриан; Чжу, Сон-Чун (август 2005 г.). «Обобщение Свендсена-Ванга на выборку произвольных апостериорных вероятностей» . Транзакции IEEE по анализу шаблонов и машинному интеллекту . 27 (8): 1239–1253. дои : 10.1109/TPAMI.2005.161 . ISSN 0162-8828 . ПМИД 16119263 . S2CID 410716 .
^ Гор, Вивек К.; Джеррум, Марк Р. (1 октября 1999 г.). «Процесс Свендсена-Ванга не всегда быстро смешивается» . Журнал статистической физики . 97 (1): 67–86. Бибкод : 1999JSP....97...67G . дои : 10.1023/А:1004610900745 . ISSN 1572-9613 . S2CID 189821827 .
^ Эдвардс, Роберт Г.; Сокал, Алан Д. (15 сентября 1988 г.). «Обобщение представления Фортюина-Кастеляна-Свенсена-Ванга и алгоритма Монте-Карло» . Физический обзор D . 38 (6): 2009–2012. Бибкод : 1988PhRvD..38.2009E . doi : 10.1103/PhysRevD.38.2009 . ПМИД 9959355 .
^ Катауделла, В.; Францезе, Г.; Никодеми, М.; Скала, А.; Конильо, А. (7 марта 1994 г.). «Критические кластеры и эффективная динамика для моделей фрустрированного спина» . Письма о физических отзывах . 72 (10): 1541–1544. Бибкод : 1994PhRvL..72.1541C . doi : 10.1103/PhysRevLett.72.1541 . HDL : 2445/13250 . ПМИД 10055635 .
^ Кандел, Дэниел; Бен-Ав, Радель; Домани, Эйтан (20 августа 1990 г.). «Динамика кластера для полностью расстроенных систем» . Письма о физических отзывах . 65 (8): 941–944. Бибкод : 1990PhRvL..65..941K . doi : 10.1103/PhysRevLett.65.941 . ПМИД 10043065 .

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

[1] Барбу, Адриан; Чжу, Сон-Чун (август 2005 г.). «Обобщение Свендсена-Ванга на выборку произвольных апостериорных вероятностей» . Транзакции IEEE по анализу шаблонов и машинному интеллекту . 27 (8): 1239–1253. дои : 10.1109/TPAMI.2005.161 . ISSN 0162-8828 . ПМИД 16119263 . S2CID 410716 .

[2] Гор, Вивек К.; Джеррум, Марк Р. (1 октября 1999 г.). «Процесс Свендсена-Ванга не всегда быстро смешивается» . Журнал статистической физики . 97 (1): 67–86. Бибкод : 1999JSP....97...67G . дои : 10.1023/А:1004610900745 . ISSN 1572-9613 . S2CID 189821827 .

[3] Эдвардс, Роберт Г.; Сокал, Алан Д. (15 сентября 1988 г.). «Обобщение представления Фортюина-Кастеляна-Свенсена-Ванга и алгоритма Монте-Карло» . Физический обзор D . 38 (6): 2009–2012. Бибкод : 1988PhRvD..38.2009E . doi : 10.1103/PhysRevD.38.2009 . ПМИД 9959355 .

[4] Катауделла, В.; Францезе, Г.; Никодеми, М.; Скала, А.; Конильо, А. (7 марта 1994 г.). «Критические кластеры и эффективная динамика для моделей фрустрированного спина» . Письма о физических отзывах . 72 (10): 1541–1544. Бибкод : 1994PhRvL..72.1541C . doi : 10.1103/PhysRevLett.72.1541 . HDL : 2445/13250 . ПМИД 10055635 .

[5] Кандел, Дэниел; Бен-Ав, Радель; Домани, Эйтан (20 августа 1990 г.). «Динамика кластера для полностью расстроенных систем» . Письма о физических отзывах . 65 (8): 941–944. Бибкод : 1990PhRvL..65..941K . doi : 10.1103/PhysRevLett.65.941 . ПМИД 10043065 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]