Исследование свойств алгоритма Ванга-Ландау тема диссертации и автореферата по ВАК РФ 01.04.07, кандидат наук Фадеева Марина Александровна

• Фадеева Марина Александровна
• кандидат наук
• 2023

Оглавление диссертации кандидат наук Фадеева Марина Александровна

1.2 Алгоритм Ванга-Ландау

1.3 Обзор модификаций алгоритма Ванга-Ландау

1.4 Модель Поттса

1.5 Матрица переходов между уровнями энергии с вероятностью Ванга-

Ландау

1.5.1 Аналитическое решение для одномерной модели Изинга

1.6 Свойства матрицы переходов

1.7 Критерий точности

1.8 Численное моделирование

1.8.1 Поведение параметров Ö и А в оригинальном алгоритме Ванг-Ландау

1.8.2 Гистограмма ровности

1.8.3 Вывод

2 Анализ характерных времен 1/t Ванга-Ландау алгоритма

2.1 Время туннелирования

2.2 Время перемешивания

3 Параллельный алгоритм Ванга-Ландау

3.1 Обзор существующих реализаций

3.1.1 Случайные блуждания по всему спектру энергии

3.1.2 Случайные блуждания по отрезкам спектра

3.1.3 Алгоритм Replica exchange Wang-Landau

3.2 Предложение и численное моделирование

3.2.1 Алгоритм Toy parallel Wang-Landau

3.2.2 Время туннелирования в окнах

3.3 Результаты моделирования

4 Применение алгоритма Ванга-Ландау для решения задачи статистической физики

4.1 Теоретическая часть и мотивация исследования

4.2 Численное моделирование

4.3 Вывод

Заключение

Список литературы

Введение диссертации (часть автореферата) на тему «Исследование свойств алгоритма Ванга-Ландау»

Введение

В последние годы высокопроизводительные вычисления приобретают все большую роль как в научных задачах, так и в практических приложениях. Эти вычисления проводятся наиболее эффективно на гибридных суперкомпьютерных системах. Особую роль при этом приобретает развитие алгоритмов и методов моделирования, которые позволяют использовать всю мощь гибридных высокопроизводительных вычислительных систем. Одним из перспективных подходов для задач моделирования является метод прямого вычисления плотности состояний, получивший название метод Ванга-Ландау. Этот метод применим для широкого класса задач - физики полимеров, в спиновых системах, а также в задачах оптимизации. Метод, несмотря на широкое его применение (более 3 тысяч цитирований оригинальной статьи [1] на Google Academy), в предложенном в оригинальной статье виде обладает ограниченной точностью. Исследование точности и применимости этого метода для решения задач на высокопроизводительных вычислительных системах является несомненно актуальной проблемой. Таким образом, проект междисциплинарный - развитие методов вычислений и применения разработанных подходов и алгоритмов для проверки теоретических гипотез статистической физики.

Цель

Разработка новых методов исследования вычислительных проблем статистической физики.

Задачи исследования

• Разработать численный метод исследования задач статистической физики с контролируемой точностью.

• Провести оценку времени туннелирования и времени перемешивания в алгоритме Ванга-Ландау.

• Разработать параллельный алгоритм с контролируемой точностью для метода Ванга-Ландау.

• Применение разработанной модификации алгоритма для изучения моделей статистической механики.

Научная новизна

1. Предложен новый математический объект для метода Ванга-Ландау - матрица переходов по дискретному спектру энергии.

2. Аналитически и численно показано, что матрица переходов стремится к стохастической при достижении необходимой точности вычисления плотности состояний.

3. Предложен критерий точности вычислений плотности состояний - отклонение старшего собственного значения матрицы переходов от единицы.

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

5. Предложена параллельная модификация с контролируемой точностью для метода Ванга-Ландау.

6. Применение разработанной методики продемонстрировано на исследовании четырехкомпонентной модели Поттса на гексагональной решетке, что позволило разрешить дискутируемый в научной литературе парадокс принадлежности этой модели к классу универсальности четырехкомпонентной модели Поттса.

Апробация результатов исследования

• "Исследование фазовых переходов в модели Поттса методом Ванга-Ландау", Russian Supercomputing Days, 27-28 сентября, 2021

• "On phase transition in four-component hexagonal lattice Potts model", CSP2020, 12-16 октября, 2020г

• "Исследование свойств алгоритма Ванга-Ландау", Межвузовская научно -техническая конференция студентов, аспирантов и молодых специалистов им.Е.В.Арменского, 19 февраля-1марта 2018г., Москва

• "Analytical structure of transition matrix in Wang-Landau algorithm", International Conference on Computer Simulation in Physics and beyond, October 9-12,2017, Moscow, Russia

Свидетельства о государственной регистрации ПО:

• Свидетельство о государственной регистрации программы

для ЭВМ №2019613934 "Реализация алгоритма Ванга-Ландау с огрублением спектра энергии".

• Свидетельство о государственной регистрации программы

для ЭВМ №2017663374 "Построение матрицы переходов для одномерной модели Изинга в алгоритме Ванга-Ландау".

Публикации автора по теме диссертации:

Публикации по теме диссертации в рецензируемых научных изданиях, входящих в международную систему цитирования WoS/Scopus:

• Barash L. Y., Fadeeva M. A., Shchur L. N. Control of accuracy in the WangLandau algorithm //Physical Review E. - 2017. - Т. 96. - №. 4. - С. 043307. (Scopus/WoS Q1)

• Fadeeva M., Shchur L. On the mixing time in the Wang-Landau algorithm //Journal of Physics: Conference Series. - IOP Publishing, 2018. - Т. 955. - №. 1. - С. 012028. (Scopus/WoS Q4)

• М.А.Фадеева, Л.Н. Щур, Моделирование четырехкомпонентной модели Потт-са на гексагональной решетке методом Ванга-Ландау с контролируемой точностью, ЖЭТФ, 2022, том 162, вып.6(12), стр. 1-8 (Scopus/WoS Q3)

Публикации по теме диссертации в рецензируемых научных изданиях, входящих в систему цитирования РИНЦ:

• М.А. Фадеева, Исследование фазовых переходов в модели Поттса методом Ванга-Ландау, Суперкомпьютерные дни в России : Труды международной конференции. 27-28 сентября 2021 г., Москва / Под. ред. Вл. В. Воеводина. - Москва : МАКС Пресс, 2021. - 192 с., стр.87-96 (РИНЦ)

Основные результаты, выносимые на защиту

• Введен новый объект в метод Ванга-Ландау - матрица переходов по дискретному спектру энергии. Продемонстрировано, что матрица стремится стать стохастической при приближении вычислений плотности состояний к точному значению.

• Разработан подход для контроля точности вычислений плотности состояний в алгоритме Ванга-Ландау.

• Впервые произведена оценка характерного времени в алгоритме Ванга-Лан-дау - времени перемешивания.

• Предложена параллельная реализация алгоритма Ванга-Ландау с контролируемой точностью. Предложен алгоритмически более простой способ "сшивки" плотности состояний всего спектра.

• Разработанный метод применен для установления вида фазового перехода в четырехкомпонентной модели Поттса на гексагональной решетке.

Краткое содержание работы

В первой главе обсуждается модификация алгоритма 1Д-Ванга-Ландау путем введения матрицы перехода между уровнями энергии с вероятностью Ванга-Ландау. На основе численных экспериментов и аналитического решения для одномерной модели Изинга показано, что матрица стремится стать дважды стохастической с ростом количества шагов алгоритма. На основе этого свойства предлагается ввести критерий точности алгоритма как отклонение старшего собственного значения матрицы от единицы.

Во второй главе анализируется оценка характерных времен модифицированного алгоритма, а именно времени туннелирования и времени перемешивания. Анализ проведен для модели Изинга и модели Поттса. Предлагается методика оценки второго этапа алгоритма на основе времени перемешивания.

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

Результат применения модифицированного метода для решения задачи статистической физики приводится в четвертой главе. Метод применен для анализа рода фазового перехода четырехкомпонентной модели Поттса на гексагональной решетке.

1 Алгоритм Ванга-Ландау и его модификация

В первой главе обсуждается модификация алгоритма 1Д-Ванга-Ландау, путем введения матрицы перехода между уровнями энергии с вероятностью Ванга-Ландау и оценка характерных времен модифицированного алгоритма.

1.1 Обзор методов Монте-Карло в статистической физике

Знание статистической суммы дает полное описание термодинамических свойств системы [2]. Статистическая сумма может быть записана в различном виде. В большом каноническом ансамбле она имеет вид

z = £

e-E(Xi)/kBT. (ц

Здесь E(Xi) энергия системы, соответствующая конфигурации Xi, к в - константа Больцмана, T - температура. Суммирование производится по всем возможным конфигурациям системы. Термодинамические функции системы можно найти из статсуммы и ее производных. Для систем с малым числом взаимодействующих частиц статсумма может быть вычислена аналитически, однако даже для системы состоящей из N элементов, каждый из которых может принимать два значения, количество возможных конфигураций растет как 2N. Соответственно вычислительная задача становится крайне сложной, поэтому на практике используют методы для численного приближения статистической суммы.

К таким методам относятся алгоритмы семейства Монте-Карло, которые основаны на различных представлениях статистической суммы. Каждому представлению статистической суммы можно сопоставить численный алгоритм для ее вычисления.

Каноническая запись (1) статистической суммы используется в первом методе семейства Монте-Карло, в алгоритме Метрополиса [3]. Этот алгоритм относится к классу методов Монте-Карло с марковскими цепями. Новое состояние системы Xm генерируется из предыдущего состояния Xk с использованием вероятности перехода, которая зависит от разности энергий между начальным и конечным состоянием A Ekm = E (Xm) — E (Xk ). Здесь E (Xm) - энергия, соответствующая конфигурации Xm, а E (Xk ) - энергия, соответствующая конфигурации Xk. Вероятность перехода в новое состояние определяется вероятностью Метрополиса

P = min[ \,eAEkm/kB T ] (2)

Алгоритм MuCa (multicanonical Monte-Carlo) основан на микроканоническом представлении статистической суммы

Ne

Z = ^ g(Ek )W (Ek ), (3)

k

где g(Ek) количество конфигураций системы с энергией Ek, W(Ek) - весовая функция, определяемая в ходе вычислений.

Кластерное представление статистической суммы [4]

Z = £ pb(1 - p)nqN (4)

bonds

дает возможность ввести алгоритмы Вольфа [5] и Свендсена-Ванга [6]. Выше p =1 — exp-J/kBT, J - константа взаимодействия между элементами системы; Nc - количество кластеров, q - количество компонент в системе.

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

Методы, основанные на микроканоническом распределении, вычисляют плотность состояний g(Ek) и не демонстрируют критического замедления.

1.2 Алгоритм Ванга-Ландау

Алгоритм Ванга-Ландау основан на микроканоническом представлении статистической суммы. Он был предложен в 2001 году и изложен в статьях [1, 7]. Он дает возможность непосредственного вычисления плотности состояний системы. Алгоритм применим для любой дискретной системы, которую можно описать конечным набором конфигурационных состояний X — X\, X2,..., Xm. Каждой конфигурации соответствует свой уровень энергии E(Xi). Для таких систем в записи статистической суммы можно перейти от суммы по конфигурациям к сумме по уровням энергии:

Z — £ g (En)e—En/kB T, (5)

En

где кв - константа Больцмана, T - температура. Функция g(En) называется плотностью состояний (DoS - density of states) системы - это количество конфигураций системы, имеющих энергию En. Такое представление статистической суммы дает возможность вычислить, например, свободную энергию и теплоемкость при любом значении температуры

E (в) = /F\ = Е NE Егд(Е)е-вЕ (6)

E (в) = (E) = THE , (6)

C (в) = e2((E2) — (E )2). (7)

Вычисление ЭоБ производится путем случайного блуждания по спектру энергии системы с вероятностью Ванга-Ландау. В процессе блуждания вычисляются две гистограммы [1]. Первая - это текущее значение логарифма плотности состояний S(Е) = \п(д(Е)). Вторая - это вспомогательная гистограмма

H(E), в которую заносится информация о количестве посещений каждого энергетического уровня. На старте алгоритма H(E) инициализируется нулями, а S(E) - единицами. Задается начальная конфигурация системы и вычисляется ее энергия Ek. Задается начальное значение параметра f = exp(1). Дальнейшие шаги алгоритма устроены следующим образом: 1) состояние системы изменяется и вычисляется энергия нового состояния Em; 2) переход из состояния с энергией Ek в состояние с энергией Em происходит с вероятностью Ванга-Ландау:

PwL(Ek, Em) = min (1,) , (8)

\ S (Em) J

где используется текущая оценка значения S(Ek) = ln g(Ek). Следующим шагом происходит обновление вспомогательной гистограммы H(Ek) ^ H(Ek) + 1, и текущей оценки S(Ek) ^ S(Ek)f. Шаг 1 и 2 повторяются до тех пор, пока гистограмма H(Ek) не станет достаточно "плоской" (например, на уровне 5% [1]). После чего значение параметра f обновляется как функция квадратного корня fi = у/fi-1, а гистограмма сбрасывается H(Ek) = 0. После чего шаги 1 и 2 снова повторяются. Алгоритм останавливается, когда параметр f достигнет некоторого выбранного значения fend.

1.3 Обзор модификаций алгоритма Ванга-Ландау

Алгоритм Ванга-Ландау получил широкое распространение и нашел применение в различных областях науки. Метод активно применяют для моделирования полимеров [8, 9] и цепочек белков [10, 11], для оптимизации [12]. Однако, несколько вопросов касательно работы и точности алгоритма требовали ответа, например: как выбрать оптимальное значение "ровности" гистограммы H(E). Как требование "плоскости" гистограммы H(E) влияет на конечную точность вычислений? Является ли выбор функции квадратного корня оптимальным для f ?

Ответ на последний вопрос был получен в двух независимых работах [13] и [12], в которых была предложена модификация алгоритма 1/t-WL и алгоритм Stochastic approximation Monte Carlo (SAMC).

В статьях [13, 14] была предложена модификация алгоритма, получившая название 1/t-Wang-Landau. Модифицированный алгоритм состоит из двух этапов. На первом этапе выполняются обычные шаги Ванг-Ландау алгоритма [1] с одним изменением: вместо проверки гистограммы H(E) на "ровность" выполняется проверка на заполненность каждого энергетического уровня H(E) = 0. Функция изменения параметра F = ln f также остается прежней Fi = Fi-1/2, пока выполняется условие Fi < Ne/t. При Fi > Ne/t алгоритм переходит на второй этап. С этого момента гистограмма H(E) не заполняется и не проверяется. Параметр F изменяется по новому правилу Fi = Ne/t. Здесь t - это

количество элементарных переворотов спина, а Ые - количество уровней системы.

Модификация БАМС [12, 15] схожа с описанной выше [13, 14]. Вводится дополнительный параметр £0 - время, когда алгоритм переходит на второй этап, измеренное в элементарных переворотах спина. Параметр Г изменяется как функция Г = —%тт. Таким образом, на первом этапе параметр Г равен единице, а на втором меняется как Г = £0/£.

Сравнительный анализ скорости сходимости метода БАМС в зависимости от параметра £0 и алгоритма 1Д-Ванга-Ландау проведен в работе [16]. Исследование было проведено для модели Изинга на квадратной решетке с линейным размером Ь = 8,16,32,64. Значения параметра £0 были взяты с кратностью от 102 до 105. Результаты вычислений для маленькой решетки Ь = 8 показали, что наиболее оптимальным является £0 = 102. В этом случае отклонение от точно-

го е(Е, £) « 1/ЫеЕ

еа1е (е)

убывает с первых итераций алгоритма. При

еа1е (е)

значениях £0 = 103,104 и выше точность сначала выходит на плато, а уже после этого отклонение е(Е, £) начинает убывать пропорционально к 1/£ . Для решетки 16 х 16 при £0 = 102 параметр е(Е, £) не сходится даже спустя £ ~ 1010 шагов. Значение £0 = 103 является оптимальным, а при больших значениях е(Е,Ь) начинает убывать только после выхода на плато. Данные наблюдения, а также результаты моделирования для решеток большего размера Ь = 32,64, указывают на критичную значимость выбора значения £0 не только на скорость, но и на факт сходимости метода в целом. Малые значения £0 не обеспечивают посещение всего спектра энергии на первом этапе, и это приводит к расходимости метода. В это же время излишне большие значения £0 замедляют скорость сходимости. В этом плане алгоритм 1Д-Ванга-Ландау имеет преимущество, так как адаптивно подбирает момент перехода на функцию Г к 1/£. Это также подтверждается численными экспериментами [16].

Выбор функции 1/£ в качестве функции изменения параметра Г имеет теоретическое обоснование. В работе [12] на основе теории стохастической аппроксимации сформулированы условия на функцию Г, необходимые для сходимости метода

то то

£ Г = то, £ Г? < то, (9)

¿=0 ¿=0

где ( Е (1, 2). В работе [17] было доказано, что наиболее оптимальным выбором функции является Г(£) к 1/£а при 1 < а < 2. Причем результаты численных экспериментов говорят о том, что а = 1 является наилучшим выбором.

Модификация 1/t-WL позволила обойти проблему с систематической ошибкой алгоритма. Проблема заключалась в том, что с ростом количества шагов алгоритма, отклонение от точного значения выходило на константное значение. Одними из первых эту проблему описали авторы в статьях [18, 19]. Было показано наличие статистической ошибки, пропорциональной квадратному корню

у/. В статье [13] также наглядно продемонстрирована ограниченная точность вычислений на примере модели Изинга. Отклонение е(Е,£) = |1 — ^"^Е) | вычисленного значения плотности состояний дп(Е,1) от точного дех(Е) оценивалось при разном количестве алгоритмических шагов £. Результаты вычислений показали, что после некоторого значения параметра Г = 1п(/) размер ошибки выходит на константу, и не уменьшается с ростом количества шагов алгоритма. Аналогичный численный эксперимент для метода 1/t-WL показал, что е(Е,Ь) убывает с ростом количества шагов пропорционально 1/Ь (см. например рис. 5).

Обзор других модификаций также показывает, что выдвинутое условие (9) на Г является критичным в сходимости метода. Например, в работе [18] были изложены соображения касательно значимости "плоскости" вспомогательной гистограммы Н(Е) в точности вычислений, а также предложена идея зафиксировать параметр Г =1 после 14 итераций. Численные эксперименты показали, что такой подход дает значимое улучшение точности только на начальных шагах алгоритма по сравнению с оригинальным методом [1], однако с увеличением количества шагов алгоритм не дает значимых улучшений.

Частота корректировки значений д(Е) также не является критичным фактором в точности вычислений. В статье [20] авторы предлагают уменьшить частоту корректировки значений д(Е) в алгоритме Ванга-Ландау с каждого переворота спина до одного Монте-Карло шага, т.е. обновлять д(Е) через каждые Ь2 элементарных переворота спина. Для оценки эффективности предложенной модификации было проведено ее сравнение с оригинальным алгоритмом Ванга-Ландау с уровнем ровности гистограммы Н(Е) 80% и 90%, а также с 1Д-модификацией. На основе сравнения результатов вычислений трех характеристик системы, а именно температуры максимума теплоемкости Тс и критических индексов в и 7, авторы пришли к выводу о том, что более редкое обновление плотности состояний по сравнению с оригинальным алгоритмом и модификацией 1-WL повышает точность алгоритма. Однако, такой подход требует в разы больше процессорного времени. Например, если сравнить результаты, полученные с помощью 1/t-WL алгоритма с критерием остановки 1п/ = 5 • 10—8 и предложенной модификации (Тс = 2.26916(12), в = 0.1259(21) и Тс = 2.26904(25), в = 0.12494(68) соответственно) , то последняя требует примерно в 7 раз больше времени [20].

В другой статье авторов [21] обсуждается подход для определения наиболее оптимального количества шагов алгоритма Ванга-Ландау. Авторы предлагают на пятой итерации алгоритма /5, при достижения ровности гистограммы Н(Е) и на основе текущей оценки плотности состояний д(Е) вычислить температуру Тс, в которой достигается максимум теплоемкости, обозначив это значение как Тс(0). Далее выполняются классические WL-шаги: гистограмма сбрасывается до нуля Н(Е) = 0, параметр также обновляется / = \/{/)— 1), и начинается следующая итерация. Но при этом добавляется модификация: при каждой сле-

дующей проверке гистограммы H(E) на ровность вычисляется Tc(t) на основе текущих значений g(E) и величина е = |Tc(t) — Tc(0)|. Идея критерия остановки по замыслу авторов заключается в том, что при выполнении условия е < limit до выполнения критерия ровности гистограммы, текущие значения g(E) сохраняются, и алгоритм останавливается. Таким образом, количество необходимых итераций задается не при запуске алгоритма, а определяется в ходе вычислений, путем задании порога на величину е. Например, для двумерной модели Изинга предлагается использовать критерий остановки е < 10—4. Условие остановки |Tc(t) — Tc(0)| < limit носит эмпирический характер и не несет под собой теоретического обоснования.

1.4 Модель Поттса

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

Модель Поттса демонстрирует фазовый переход первого или второго рода в зависимости от числа компонент q. При q > 4 модель демонстрирует фазовый переход первого рода, с разрывом энергии при температуре фазового перехода. При q < 4 - фазовый переход второго рода [53].

При этом класс универсальности вблизи критической точки определяется числом компонент q. Для перехода второго рода свойственно изменение симметрии вещества. Для адсорбированных монослоев была предложена классификация непрерывных фазовых переходов в зависимости от строения симметрии вещества [24] - [26], основанная на теории Ландау о фазовых переходов второго рода [2]. Было установлено, что переходы между упорядоченной и неупорядоченной фазой в адсорбированных слоях относятся к небольшому числу классов универсальности, а именно к классу двумерной модели Изинга (q = 2), трех-или четырехкомпонентной модели Поттса (q = 3,4) или xy-модели.

Двумерная модель Поттса с четырьмя компонентами была экспериментально реализована в виде адсорбации кислорода на гексагональной поверхности Ru(001) со структурой p(2 х 2). Значения критических индексов а, в, j, v были определены при температуре 0.004 < t < 0.1. Полученные значения согласуются с аналитическими значениями четырехкомпонентной модели Поттса с точность 3%-10% [27].

Гамильтониан модели Поттса [22] c q-компонентами имеет вид

H = — £ 5(at,aj), (10)

<i,j>

где сумма производится по всем ближайшим соседям. Здесь 5 - символ Кроне-кера, принимает q-различных значений.

В общем случае модель Поттса можно рассматривать с различными граничными условиями, например, с периодическим, открытыми или закрытыми. Решения для таких случаев будут отличаться. В данной работе будет рассматриваться модель с периодическими граничными условиями, так как в этом случае влияние конечного размера системы минимально при численных расчетах.

Модель Изинга

Модель Изинга - частный случай модели Поттса с д = 2. Это простейшая модель ферромагнетика, предложенная Ленцем и решенная в одномерном случае Изингом в 1925 [23]. В 1944г. Онзагер получил точное решение для решетки размером Ь х М в двумерном случае [28] с периодическими граничными условиями при нулевом внешнем магнитном поле.

а)

Рис. 1: Одномерная модель Изинга Ш (а) и двумерная модель Изинга (Ь)

Модель Изинга в данной работе будет рассматриваться с периодическими граничными условиями. В одномерном случае она представляет собой замкнутую цепочку, состоящую из Ь спинов ог, ог = ±1. В двумерном случае представляет собой решетку на торе, в узлах которой расположены спины, принимающие значения = ±1 (рис.1). В общем виде гамильтониан системы вычисляется как

ь

Н = —— Н^о (11)

г=1 г

где оь+1 = о1, J - константа взаимодействия между спинами, Н - внешнее магнитное поле. Здесь и далее для простоты примем J = 1, Н = 0.

1.5 Матрица переходов между уровнями энергии с вероятностью Ванга-Ландау

Оригинальный алгоритм Ванга-Ландау [1] не предлагает метода для оценки точности алгоритма, кроме эвристического критерия ровности гистограммы

Н(Е). В данном разделе будет изложен подход для определения критерия точности алгоритма. Раздел основан на статье [29].

Вспомогательная функция Н(Е) накапливает информацию только о суммарном количестве посещений каждого уровня энергии, однако не отражает информации о том, между какими уровнями был совершен переход.

Введем понятие Матрицы переходов между уровнями энергии в алгоритме Ванг-Ландау. Это квадратная матрица, размер которой равен количеству уровней в системе Ые. Ее элементы - это вероятности перейти с одного уровня энергии на другой при случайном блуждании по спектру энергии. Для одномерной (( = 1) модели Изинга Ые = Ь/2 + 1, для двумерной (( = 2) модели -Ые = Ь2 — 1. Случайные блуждания по спектру энергии модели Изинга устроены таким образом, что за один шаг возможен переход не дальше ( -уровней. Соответственно, каждая строка и столбец матрицы переходов Т(Ек, Ето) содержат 2( + 1 не нулевой элемент.

1.5.1 Аналитическое решение для одномерной модели Изинга

Элементы матрицы, лежащие не на диагонали к = т, определяются выражением

Т(Ек, Ет) = шт Р(Ек, Ет). (12)

Первая компонента - это вероятность Ванга-Ландау PwL = шт ^1, ^Е))

перейти с одного энергетического уровня на другой. Вторая компонента Р(Ек, Ет) - это вероятность перехода из конфигурации системы с энергией Ек в конфигурацию системы с энергией Ет. Значение Р(Е], Ет) зависит от размера системы и локальной конфигурации решетки.

Аналитическое решение Р(Е],Ет) было найдено для одномерной модели Изинга размером Ь с периодическими граничными условиями

Р (Ек ,Ет) = &-¿(Е)-■ (13)

Здесь к - количество пар доменных стенок в конфигурации. Под доменной стенкой понимается место, где у последовательно расположенных спинов меняется знак. Другими словами, доменные стенки делят спины на группы последовательно расположенных спинов с одинаковым знаком. Одна пара стенок - две группы, две пары - четыре группы и т.д. Количество и расположение доменных стенок определяют энергию конфигурации Ек = — = — Ь + 4к, где к = 0,..., Ь/2. Ы^к,Ь) - количество конфигураций системы, в которых ¿-спинов изолированы по одному доменными стенками, а остальные 2к — г пар стенок образуют группы спинов, состоящие из двух и более спинов с одинаковым знаком, а QEk^Em - это вероятность перейти с такой конфигурации на

Список литературы диссертационного исследования кандидат наук Фадеева Марина Александровна, 2023 год

Список литературы

[1] Wang F., Landau D. P. Efficient, multiple-range random walk algorithm to calculate the density of states //Physical review letters. - 2001. - Т. 86. - №. 10.

- С. 2050.

[2] Ландау Л. Д., Лифшиц Е. М. Статистическая физика. Часть 1. Том 5. -1964.

[3] Metropolis N., Ulam S. The monte carlo method //Journal of the American statistical association. - 1949. - Т. 44. - №. 247. - С. 335-341.

[4] Fortuin C. M., Kasteleyn P. W. On the random-cluster model: I. Introduction and relation to other models //Physica. - 1972. - Т. 57. - №. 4. - С. 536-564.

[5] Wolff U. Lattice field theory as a percolation process //Physical review letters.

- 1988. - Т. 60. - №. 15. - С. 1461.

[6] Swendsen R. H., Wang J. S. Nonuniversal critical dynamics in Monte Carlo simulations //Physical review letters. - 1987. - Т. 58. - №. 2. - С. 86.

[7] Wang F., Landau D. P. Determining the density of states for classical statistical models: A random walk algorithm to produce a flat histogram //Physical Review E. - 2001. - Т. 64. - №. 5. - С. 056101.

[8] Zablotskiy S. V., Ivanov V. A., Paul W. Multidimensional stochastic approximation Monte Carlo //Physical Review E. - 2016. - Т. 93. - №. 6. -С. 063303.

[9] Mark P. Taylor, Wolfgang Paul, Kurt Binder Phase transitions of a single polymer chain: A Wang-Landau simulation study //J. Chem. Phys. 131, 114907 (2009)

[10] Rastogi C. et al. Accurate and sensitive quantification of protein-DNA binding affinity //Proceedings of the National Academy of Sciences. - 2018. - Т. 115. -№. 16. - С. E3692-E3701.

[11] Wüst T., Reith D., Virnau P. Sequence determines degree of knottedness in a coarse-grained protein model //Physical review letters. - 2015. - Т. 114. - №. 2.

- С. 028102.

[12] Liang F. A theory on flat histogram Monte Carlo algorithms //Journal of statistical physics. - 2006. - Т. 122. - №. 3. - С. 511-529.

[13] Belardinelli R. E., Pereyra V. D. Fast algorithm to calculate density of states //Physical Review E. - 2007. - Т. 75. - №. 4. - С. 046701.

[14] Belardinelli R. E., Pereyra V. D. Wang-Landau algorithm: A theoretical analysis of the saturation of the error //The Journal of chemical physics. - 2007. - T. 127. - №. 18. - C. 184105.

[15] Liang F., Liu C., Carroll R. J. Stochastic approximation in Monte Carlo computation //Journal of the American Statistical Association. - 2007. - T. 102. - №. 477. - C. 305-320.

[16] Schneider S., Mueller M., Janke W. Convergence of Stochastic Approximation Monte Carlo and modified Wang-Landau algorithms: Tests for the Ising model //Computer Physics Communications. - 2017. - T. 216. - C. 1-

[17] Zhou C. et al. Optimal modification factor and convergence of the Wang-Landau algorithm //Physical Review E. - 2008. - T. 78. - №. 4. - C. 046705.

[18] Lee H. K., Okabe Y., Landau D. P. Convergence and refinement of the Wang-Landau algorithm //Computer physics communications. - 2006. - T. 175. - №. 1. - C. 36-40.

[19] Zhou C., Bhatt R. N. Understanding and improving the Wang-Landau algorithm //Physical Review E. - 2005. - T. 72. - №. 2. - C. 025701. 7.

[20] Caparica A. A., Cunha-Netto A. G. Wang-landau sampling: Improving accuracy //Physical Review E. - 2012. - T. 85. - №. 4. - C. 046702.

[21] Caparica A. A. Wang-Landau sampling: A criterion for halting the simulations //Physical Review E. - 2014. - T. 89. - №. 4. - C. 043301.

[22] Potts R. B. Some generalized order-disorder transformations //Mathematical proceedings of the cambridge philosophical society. - Cambridge University Press, 1952. - T. 48. - №. 1. - C. 106-109.

[23] Ising E. Beitrag zur theorie des ferromagnetismus //Zeitschrift f"ur Physik A Hadrons and Nuclei.1925.T. 31. №. 1.C. 253-258.

[24] Domany E. et al. Classification of continuous order-disorder transitions in adsorbed monolayers //Physical Review B. - 1978. - T. 18. - №. 5. - C. 2209.

[25] Domany E., Schick M. Classification of continuous order-disorder transitions in adsorbed monolayers. II //Physical Review B. - 1979. - T. 20. - №. 9. - C. 3828.

[26] Rottman C. Symmetry classification of continuous phase transitions in two dimensions //Physical Review B. - 1981. - T. 24. - №. 3. - C. 1482.

[27] Pfnür H., Piercy P. Critical behavior of p (2x 2) oxygen on Ru (001): An example of four-state Potts critical exponents //Physical Review B. - 1989. - T. 40. - №. 4. - C. 2515.

[28] Onsager L. Crystal statistics. I. A two-dimensional model with an order-disorder transition //Physical Review. - 1944. - Т. 65. - №. 3-4. - С. 117.

[29] Barash L. Y., Fadeeva M. A., Shchur L. N. Control of accuracy in the WangLandau algorithm //Physical Review E. - 2017. - Т. 96. - №. 4. - С. 043307.

[30] Ф.Р. Гантмахер, Теория матриц. Наука, М., 1967г. с.354-362.

[31] M. Krainiuk, M. Goli, and V.R. Pascuzzi, oneAPI Open-Source Math Library Interface, 2021 International Workshop on Performance, Portability and Productivity in HPC (P3HPC), p. 22.

[32] M.S. Guskova, L.Yu. Barash, L.N. Shchur, RNGAVXLIB: Program library for random number generation, AVX realization, Comp. Phys. Commun. 200 402 (2016).

[33] Beale P.D. Exact Distribution of Energies in the Two-Dimensional Ising Model //Physical review letters.1996.T.76.№. 1.С. 78.

[34] Dayal P. et al. Performance limitations of flat-histogram methods //Physical Review Letters. - 2004. - Т. 92. - №. 9. - С. 097201.

[35] Fadeeva M., Shchur L. On the mixing time in the Wang-Landau algorithm //Journal of Physics: Conference Series. - IOP Publishing, 2018. - Т. 955. - №. 1. - С. 012028.

[36] Redner S. A guide to first-passage processes. - Cambridge university press, 2001.

[37] S. Boyd, P. Diaconis, L. Xiao, Fastest mixing Markov chain on a graph, SIAM Review

[38] Zhan L. A parallel implementation of the Wang-Landau algorithm //Computer Physics Communications. - 2008. - Т. 179. - №. 5. - С. 339-344.

[39] Khan M. O., Kennedy G., Chan D. Y. C. A scalable parallel Monte Carlo method for free energy simulations of molecular systems //Journal of computational chemistry. - 2005. - Т. 26. - №. 1. - С. 72-77.

[40] Yin J., Landau D. P. Massively parallel Wang-Landau sampling on multiple GPUs //Computer Physics Communications. - 2012. - Т. 183. - №. 8. - С. 1568-1573.

[41] Vogel T. et al. Generic, hierarchical framework for massively parallel WangLandau sampling //Physical review letters. - 2013. - Т. 110. - №. 21. - С. 210603.

[42] Perera D. et al. Replica-Exchange Wang—Landau Sampling: Pushing the Limits of Monte Carlo Simulations in Materials Sciences //TMS 2015 144th Annual Meeting Exhibition. - Springer, Cham, 2015. - С. 811-818.

[43] Hukushima K., Nemoto K. Exchange Monte Carlo method and application to spin glass simulations //Journal of the Physical Society of Japan. - 1996. - Т. 65. - №. 6. - С. 1604-1608.

[44] Earl D. J., Deem M. W. Parallel tempering: Theory, applications, and new perspectives //Physical Chemistry Chemical Physics. - 2005. - Т. 7. - №. 23. -С. 3910-3916.

[45] Hansmann U. H. E. Parallel tempering algorithm for conformational studies of biological molecules //Chemical Physics Letters. - 1997. - Т. 281. - №. 1-3. - С. 140-150.

[46] Y. Sugita and Y. Okamoto, Chem. Phys. Lett., 1999, 314, 141.

[47] Sugita Y. et al. Replica-exchange methods for biomolecular simulations //Biomolecular Simulations. - Humana, New York, NY, 2019. - С. 155-177.

[48] Vogel T. et al. Scalable replica-exchange framework for Wang-Landau sampling //Physical Review E. - 2014. - Т. 90. - №. 2. - С. 023302.

[49] Li Y. W. et al. A new paradigm for petascale Monte Carlo simulation: Replica exchange Wang-Landau sampling //Journal of Physics: Conference Series. - IOP Publishing, 2014. - Т. 510. - №. 1. - С. 012012.

[50] Vogel T. et al. Exploring new frontiers in statistical physics with a new, parallel Wang-Landau framework //Journal of Physics: Conference Series. - IOP Publishing, 2014. - Т. 487. - №. 1. - С. 012001.

[51] Moreno F., Davis S., Peralta J. A portable and flexible implementation of the Wang-Landau algorithm in order to determine the density of states //Computer Physics Communications. - 2022. - Т. 274. - С. 108283.

[52] М.А.Фадеева, Л.Н. Щур, Моделирование четырехкомпонентной модели Поттса на гексагональной решетке методом Ванга-Ландау с контролируемой точностью, ЖЭТФ, 2022, том 162, вып.6(12), стр. 1-8

[53] Baxter R. J. Potts model at the critical temperature //Journal of Physics C: Solid State Physics. - 1973. - Т. 6. - №. 23. - С. L445.

[54] Feldmann H. et al. Study of the Potts model on the honeycomb and triangular lattices: Low-temperature series and partition function zeros //Journal of Physics A: Mathematical and General. - 1998. - Т. 31. - №. 10. - С. 2287

[55] M. Fisher, The renormalization group in the theory of critical behavior, Rev. Mod. Phys. 46 597 (1974).

[56] V. Privman, P.C. Hohenberg, A. Aharony, in Phase Transitions and Critical Phenomena, Vol. 14, edited by C. DüMB AND J.L. Lebowitz (Academic, New York, 1991).

[57] J.L. Cardy, Conformal invariance and universality in finite-size scaling, J. Phys. A: Math. Gen. 17 L385 (1984).

[58] F.Y. Wu, The Potts model, Rev. Mod. Phys. 54 235 (1982).

[59] L.N. Shchur, B. Berche, P. Butera, Numerical revision of the universal amplitude ratios for the two-dimensional 4-state Potts model, Nucl. Phys. B 811 491 (2009).

[60] M. Sokolowski and H. Pfnür, Continuous order-disorder phase transitions of the p(2 x 2) and (л/3 x л/3) R30 superstructures of sulfur on Ru(001): Effective critical exponents and finite-size effects, Phys. Rev. B 49 7716 (1994).

[61] Муртазаев А. К. и др. ФАЗОВЫЕ ПЕРЕХОДЫ И ТЕРМОДИНАМИЧЕСКИЕ СВОЙСТВА МОДЕЛИ ПОТТСА С ЧИСЛОМ СОСТОЯНИЙ СПИНА q= 4 НА ГЕКСАГОНАЛЬНОЙ РЕШЕТКЕ //ЖЭТФ. - 2019. - Т. 156.

- С. 502-506.

[62] Ramazanov M. K. et al. Phase transitions and the magnetic properties of the Potts model with four spin states on a hexagonal lattice in low magnetic fields //JETP Letters. - 2021. - Т. 114. - №. 11. - С. 693-698.

[63] Binder K. Finite size scaling analysis of Ising model block distribution functions // Zeitschrift für Physik B Condensed Matter, 43 119 (1981).

[64] Landau D., Binder K. A guide to Monte Carlo simulations in statistical physics.

- Cambridge university press, 2021., c.80

[65] Janke W. First-order phase transitions //Computer Simulations of Surfaces and Interfaces. - 2003. - С. 111-135.

[66] Cardy J. L., Nauenberg M., Scalapino D. J. Scaling theory of the Potts-model multicritical point //Physical Review B. - 1980. - Т. 22. - №. 5. - С. 2560.

[67] Salas J., Sokal A. D. Logarithmic corrections and finite-size scaling in the two-dimensional 4-state Potts model //Journal of statistical physics. - 1997. - Т. 88.

- №. 3. - С. 567-615.

[68] A.E. Ferdinand and M.E. Fisher, Bounded and inhomogeneous Ising models. I. Specific-heat anomaly of a finite lattice, Phys. Rev. 185 832 (1969).

[69] Enting I. G. Critical exponents for the four-state Potts model //Journal of Physics A: Mathematical and General. - 1975. - T. 8. - №. 4. - C. L35.

[70] Shchur, Lev N. and Fadeeva, Marina A., Properties of Parallel Wang-Landau Algorithm with Transition Matrix Control. http://dx.doi.org/10.2139/ssrn.4497091