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

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

Исходный алгоритм был разработан для Я пою и модели Поттса, а позже она была обобщена и на другие системы, такие как модель XY Алгоритм Вольфа и частицы жидкости. Ключевым ингредиентом был случайная кластерная модель, представление Изинга или Potts модель через перколяционные модели соединительных связей, разработанные Фортуном и Кастелейном. Барбу и Чжу (2005) обобщили его на случай произвольной вероятности выборки, рассматривая его как Алгоритм Метрополиса – Гастингса и вычисление вероятности принятия предложенного хода Монте-Карло.

Мотивация

Проблема критического замедления, влияющего на локальные процессы, имеет фундаментальное значение при изучении второго порядка. фазовые переходы (как ферромагнитный переход в Модель Изинга ), поскольку увеличение размера системы для уменьшения эффектов конечного размера имеет недостаток, заключающийся в том, что для достижения теплового равновесия требуется гораздо большее количество перемещений. Действительно время корреляции ${displaystyle au}$ обычно увеличивается как ${displaystyle L ^ {z}}$ с ${displaystyle zsimeq 2}$ или выше; так как, чтобы быть точным, время моделирования должно быть ${displaystyle tgg au}$ , это основное ограничение размера систем, которые можно изучать с помощью локальных алгоритмов. Алгоритм SW первым дал необычно малые значения для динамических критических показателей: ${displaystyle z = 0,35}$ для 2D-модели Изинга ( ${displaystyle z = 2,125}$ для стандартных расчетов); ${displaystyle z = 0,75}$ для 3D-модели Изинга, в отличие от ${displaystyle z = 2,0}$ для стандартных симуляций.

Описание

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

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

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

  ${displaystyle Pleft [b_ {n, m} = 0 | sigma _ {n} eq sigma _ {m} ight] = 1}$ ;  ${displaystyle Pleft [b_ {n, m} = 1 | sigma _ {n} eq sigma _ {m} ight] = 0}$ ;  ${displaystyle Pleft [b_ {n, m} = 0 | sigma _ {n} = sigma _ {m} ight] = e ^ {- 2 eta J_ {nm}}}$ ;  ${displaystyle Pleft [b_ {n, m} = 1 | sigma _ {n} = sigma _ {m} ight] = 1-e ^ {- 2 eta J_ {nm}}}$ ;

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

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

${displaystyle H [sigma] = ограничения суммы _ {} - J_ {i, j} sigma _ {i} sigma _ {j}}$ ,

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

${displaystyle Z = сумма пределов _ {lbrace sigma brace} e ^ {- eta H [sigma]}}$ .

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

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

${displaystyle Z_ {n, m} ^ {same} = ограничения суммы _ {lbrace sigma brace} e ^ {- eta H_ {nm} [sigma]} дельта _ {sigma _ {n}, sigma _ {m}}}$ ;

${displaystyle Z_ {n, m} ^ {diff} = сумма пределов _ {lbrace sigma brace} e ^ {- eta H_ {nm} [sigma]} слева (1-дельта _ {sigma _ {n}, sigma _ { мог бы).}$

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

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

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

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

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

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

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

Правильность

Можно показать, что этот алгоритм приводит к равновесным конфигурациям. Первый способ доказать это - использовать теорию Цепи Маркова, либо отмечая, что равновесие (описываемое Больцман -Распределение Гиббса) отображается в себя, или показывает, что за один проход решетки существует ненулевая вероятность перехода от любого состояния цепи Маркова к любому другому; таким образом, соответствующая неприводимая эргодическая цепь Маркова имеет асимптотическое распределение вероятностей, удовлетворяющее подробный баланс.

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

${displaystyle {frac {P_ {lbrace sigma brace ightarrow lbrace sigma 'brace}} {P_ {lbrace sigma' brace ightarrow lbrace sigma brace}}} = {frac {Prleft (lbrace sigma 'brace | BCight) Prleft (BC | lbrace) sigma brace ight)} {Prleft (lbrace sigma brace | BCight) Prleft (BC | lbrace sigma 'brace ight)}} = {frac {pcdot exp left [-2 ограничения суммы этажа _ {} delta _ {sigma _ {l}, sigma _ {m}} J_ {lm} ight]} {pcdot exp left [-2 ограничения суммы eta _ {} delta _ {sigma '_ {l}, sigma' _ {m}} J_ {lm} ight]}} = e ^ {- eta Delta E}}$

поскольку ${displaystyle Delta E = -sum limits _ {} J_ {lm} left (sigma '_ {l} sigma' _ {m} -sigma _ {l} sigma _ {m} ight) = - сумма пределы _ {} J_ {lm} left [delta _ {sigma '_ {l}, sigma' _ {m}} - слева (1-delta _ {sigma '_ {l}, sigma' _ {m}} ight) -delta _ {sigma _ {l}, sigma _ {m}} + left (1-delta _ {sigma _ {l}, sigma _ {m}} ight) ight] = - 2 суммы пределов _ {} J_ {lm} влево (delta _ {sigma '_ {l}, sigma' _ {m}} - delta _ {sigma _ {l}, sigma _ {m}} ight)}$ .

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

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

Хотя это не ясно аналитически из оригинальной статьи, причина, по которой все значения z, полученные с помощью алгоритма SW, намного ниже, чем точная нижняя граница для алгоритмов однократного переворота ( ${displaystyle zgeq gamma / u}$ ) заключается в том, что расхождение корреляционной длины строго связано с образованием перколяционных кластеров, которые переворачиваются вместе. Таким образом, время релаксации значительно сокращается.

Алгоритм неэффективен при моделировании разочарованные системы.

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

Содержание

Мотивация

Описание

Правильность

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

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

Рекомендации