Подсчет гамильтоновых циклов на прямоугольных решетках, цилиндрах и торах методом матрицы переноса

Караваев, Артем Михайлович

Подсчет гамильтоновых циклов на прямоугольных решетках, цилиндрах и торах методом матрицы переноса тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Караваев, Артем Михайлович АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Петрозаводск МЕСТО ЗАЩИТЫ

2012 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

Диссертация по математике на тему «Подсчет гамильтоновых циклов на прямоугольных решетках, цилиндрах и торах методом матрицы переноса»

Автореферат диссертации на тему "Подсчет гамильтоновых циклов на прямоугольных решетках, цилиндрах и торах методом матрицы переноса"

Санкт-Петербургский государственный университет

0050153ии

КАРАВАЕВ Артем Михайлович

Подсчет гамильтоновых циклов на прямоугольных решетках, цилиндрах и торах методом матрицы переноса

01.01.09 — дискретная математика и математическая кибернетика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

1 2 201

Санкт-Петербург 2012

005015300

Работа выполнена на кафедре прикладной математики и кибернетики Петрозаводского государственного университета

Научный руководитель: кандидат физико-математических наук,

доцент перепечко Сергей Николаевич Официальные оппоненты: доктор физико-математических наук, профессор

романовский Иосиф Владимирович (Санкт-Петербургский государственный университет) . доктор физико-математических наук, профессор одинец Владимир Петрович (Коми государственный педагогический институт) : Ведущая организация: Учреждение Российской академии наук

Санкт-Петербургское отделение ■ Математического института имени В. А. Стеклова РАН :

Защита состоится » ^(0рТсХ 2012 г. в № часов на заседании совета Д212.232.29 по защите докторских и кандидатских диссертаций при Санкт-Петербургском государственном университете по адресу: 199034, Санкт-Петербург, Университетская наб., 7/9., ауд. 133.

С диссертацией можно ознакомиться в Научной библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., 7/9.

Автореферат разослан »срв^ра^З- 2012 г.

Ученый секретарь диссертационного совета, доктор физико-математических наук, , профессор (/

Нежинский В. М.

Общая характеристика работы

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

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

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

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

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

1. Проанализировать и систематизировать известные результаты, выявив их достоинства и недостатки.

2. Разработать параллельную версию алгоритма, объединив достоинства существующих реализаций с новыми методами сжатия матрицы переноса, для максимального расширения набора известных данных.

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

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

5. Существенно увеличить точность определения константы связности по сравнению с известными методами.

6. Проверить корректность выводов полевой 0(п) модели среднего поля, предполагающей сворачивание решетки в тор с последующим сведением дискретной задачи к непрерывной.

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

1. Разработана эффективная схема кодирования состояний для подсчета числа гамильтоновых циклов на прямоугольных решетках "?т х СР„, цилиндрах С,„ х Уп и торах Ст х С„, на основе которой предложен новый параллельный алгоритм.

2. Расширен набор точных значений для количества циклов на решетках, цилиндрах и торах.

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

4. Уточнено значение универсальной константы связности для всех трех рассматриваемых семейств графов: и = 1.472 799 ± 0.000003.

5. Показано, что асимптотика количества циклов на торах Ст х. С„ при п —> оо имеет качественно иной вид, нежели на решетках Тт X Тп и цилиндрах Ст х Уп, раздваиваясь при четном т, что свидетельствует о необходимости уточнения основных принципов проведения расчетов в рамках стандартной 0(п) модели среднего поля.

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

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

Достоверность научных положений подтверждается тем, что разработанные методы успешно воспроизводят уже известные результаты, а многие новые результаты остаются в русле прогнозов, сделанных авторами преды-

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

Апробация. Основные положения диссертационной работы докладывались и обсуждались на международных конференциях по параллельным вычислениям «Высокопроизводительные параллельные вычисления на кластерных системах» (2009) и «Параллельные вычислительные технологии» (в 2010 и 2011 г.), на международной конференции по вычислительной механике и современным прикладным программным системам (ВМСППС '2011), на конференции «Математика, экономика, менеджмент: 100 лет со дня рождения Л. В. Канторовича», на научном семинаре кафедры исследования операций математико-механического факультета СПбГУ под руководством зав. каф. д. ф.-м. н., профессора Н. Н. Петрова (в 2010 и 2011 г.), а также на научных семинарах кафедры прикладной математики и кибернетики ПетрГУ.

Публикация результатов. Результаты исследований отражены в работах 1-14. В работе 4 соискателю принадлежит вторая часть, посвященная параллельной реализации формул для подсчета циклов на языке «Си» и проведение вычислительных экспериментов. Соавтору принадлежит первая часть работы. В работе 11 соискателю принадлежит разработка алгоритма и проведение всех расчетов с его помощью, а также вывод рекуррентных соотношений и явная формула для случая т = 3. Соавтору принадлежат остальные результаты. Статьи 1 и 2 опубликованы в журналах, входящих в Перечень рецензируемых научных журналов и изданий.

Объем и структура работы. Диссертация состоит из введения, раздела с терминологией, четырех глав, заключения и списка источников. Общий объем диссертации составляет 145 страниц (включая библиографию из 52 источников). Работа содержит 36 иллюстраций и 21 таблицу.

Содержание работы

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

Описание главы 1

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

Для больших сеточных графов порядка N = тп считается, что количество циклов можно оценить величиной , где В — число вершин графа, лежащих на его «границе», а символом х обозначена универсальная константа связности. В физических приложениях ее вычисление представляет основной интерес, поскольку к связана с энтропией, приходящейся на один узел решетки. Предполагается, что значение к для решеток и цилиндров одинаково, однако коэффициент ц < 1 будет для этих семейств графов различным.

В этом же разделе обсуждаются различные подходы к оценке величины х. Один из них основан на вычислении предела последовательности (хт) при тп —»■ оо, в которой хт — значение константы связности для сеточного графа с фиксированным значением параметра т и п —оо.

Другой подход основан на полевой О(п) модели среднего поля, трансформирующей решетку Ут х Уп в тор Ст х Сп путем наложения циклических граничных условий. Вычисления в рамках данной модели позволяют вывести аналитическое выражение для константы связности = 4/е ~ 1.4715.

Точность полученного результата на протяжении ряда лет оставалась неиз-

вестной, и наиболее точное значение, известное в настоящее время, равно1 х= 1.472801 ±0.000010.

Третий раздел главы посвящен обзору литературы, в которой метод матрицы переноса применялся для подсчета циклов в рассматриваемых семействах графов. Отмечаются недостатки ранних работ, в которых прямолинейное применение метода приводило к тому, что порядок матрицы переноса оценивался сверху числами Моцкина, асимптотика которых имеет вид у/3/(47гш3) • 3ra. Основным выводом небольшого четвертого раздела является констатация того факта, что параллельных реализаций метода матрицы переноса для задачи подсчета циклов неизвестно.

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

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

Описание главы 2

Глава начинается с изложения теоретических основ метода матрицы переноса. Показывается, что задача подсчета циклов сводится к подсчету маршрутов между заданной парой вершин в некотором псевдографе, множество вершин которого совпадает с множеством всех достижимых состояний. Описанный в разделе 2.3.1 алгоритм ConSTRUCT-GrAPH строит такое множество. В результате работы алгоритма удается получить матрицу, порядок которой в 2-3 раза меньше границы, определяемой числами Моцкина Мт.

1 Jacobscn J. Ь. Kondcv J. Field theory of compact polymers on the square lattice. Nuclear Physics, 1998.

Vol. B532[FS|. P. 635-688.

Вторая важная особенность алгоритма, не использовавшаяся ранее, заключается в отождествлении симметричных состояний. Это позволяет еще вдвое сократить порядок матрицы переноса при подсчете циклов на решетках Ут х Уп. Для цилиндров Ст х Уп уменьшение порядка матрицы при учете симметрии варьируется от т/2 до m раз. Например, для m = 12 количество слов Моцкина равно 15 511. Количество достижимых состояний составляет 7281, а с учетом симметрии остается всего 3 774, то есть в 4 раза меньше, чем слов Моцкина. Для случая цилиндров число состояний снижается более радикально — до 619 (в 25 раз меньше, чем слов Моцкина).

При m = 3 или m = 4 метод может быть применен в «ручном» режиме, позволяя в деталях проиллюстрировать все его основные особенности, включая вывод рекуррентных соотношений и нахождение асимптотики числа циклов. Для m = 3, 4 подробно изучены все три семейства сеточных графов Ут х 9п, Ст х Уп и Ст х еп (теоремы 2.2-2.7). Если для двух первых семейств полученные формулы согласуются с ранее известными, то явные выражения для числа циклов на торах получены впервые. Эти результаты можно сформулировать следующим образом.

Теорема 2.6 Количество циклов на торе 63 х 6п подчиняется формуле

[е3 х е„] On = 3" + In - 2" + + (-1)" - 4, п z 3:

Теорема 2.7 Количество циклов на торе S4 х С„ вычисляется по формуле

[е4 х е„] сц = А(п) + ап mod2(L«/2j),

в которой

А(п) = (2п -h 1) ■ ch(2п ■ Arth y/ljl) -

- (n/V3) • sh(2n • Arth ,/Щ) + cos(tt • n/2) - sin(7r • n/2), a0(n) = (4n - 16 ■ 3" - 4)/3 + 8 • 2"'2 ■ cos(n • arctg y/7) +

+ 4 • 2" • ch(2n • Arth s/Щ) - 2 • ch(2n • Arth y/lß), a1(n) = -2-(n + l)-(2-(-l)n).

Асимптотика числа циклов при n —> 00 раздваивается в зависимости от четности п:

[е4 х е„] о„ ~

2 (2 + л/б)", если п четно,

((1- 2Тз)п + |) (2 + л/3)", еслип

если п нечетно.

Предсказать раздвоение асимптотики в рамках полевой 0(п) модели никогда ранее не удавалось.

Описание главы 3

Глава начинается с описания схемы кодирования состояний на решетках и цилиндрах. В терминах «правильных скобочных последовательностей, разреженных нулями» (ПСПРН) показывается, что основные принципы кодирования для этих семейств совпадают, что может быть сформулировано как Теорема 3.3 Способы кодирования состояний для решеток и цилиндров идентичны в том смысле, что любое допустимое состояние для обоих семейств графов может быть закодировано с помощью ПСПРН.

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

Отмечается, что существует три типа выбора комбинаций горизонтальных ребер, которые нарушают условие гамильтоновости и, следовательно, являются недопустимыми. Учет таких случаев позволяет сократить перебор с 2т_1 вариантов до /т, где /т — число Фибоначчи с индексом т.

Рассмотренная в начале главы схема кодирования легла в основу алгоритма подсчета циклов, который можно использовать как в случае решеток, так и цилиндров. Опора на принципы динамического программирования приводит к такой реализации, когда оперативная память компьютера расходуется весьма экономно. Однако платой за это является необходимость многократного перевычисления списков То (б). Сокращение времени расчетов достигается за счет перехода к параллельным вычислениям. Приводимая в тексте оценка сложности 0(п ■ 6т/т3/2) (теорема 3.5) оказывается несколько пессимистичной, поскольку не учитывает серию оптимизаций в коде алгоритма.

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

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

Каждое состояние может содержать цепи двух типов. Цепи первого типа обоими концами касаются одного уровня и проходят через прошлое. При изображении состояния они выглядят как дугообразные линии. Цепи второго типа начинаются у первого слоя и заканчиваются у текущего. Они изображаются в виде отрезков, соединяющих вершины нижнего и верхнего слоя на «сжатом» торе. Скобки соответствуют цепям первого типа, а числа — концам цепей второго типа. Пример такого кодирования показан на рис. 1.

Количество циклов растет экспоненциально с увеличением параметров сеточных графов. Так, на решетке 7 22 х У 22 оно составляет (71 знак) 13 404 209 505 893 761748 339 786 653 564 937 498 745 897123 531041248 680 272 448 954 956.

Чтобы не хранить длинные числа в памяти, использовалась модулярная арифметика. Вычисления проводились по модулю различных простых чисел, близких к 231 — 1, из-за чего программу приходилось запускать несколько раз. Например, для получения указанного выше числа циклов потребовалось 8 простых чисел от 231 — 151 до 231 — 1 включительно.

" ""Г

3 -1-н к- -►.Д. -Ч ► —Ч И-

[ 12 3 45678

( )

ач-Ч-НН-Ч"

2 3 4 5 6 (а)

(б)

РИСУНОК 1 — Кодирование состояний на торе: (а) Сжатие фрагмента тора; (б) Кодирование сжатого фрагмента двумя строками символов

Результатом работы алгоритма стало точное решение задачи о подсчете циклов на решетках 1Рт х и цилиндрах Ст х для всех 3 ^ т < 22 и 1 ^ п < 100, а также для торов ет х для всех 3<т^10и3<п< 500.

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

Описание главы 4

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

Применение алгоритма позволило вывести рекуррентные соотношения для числа циклов на решетках Тт х 7п для т < 14, цилиндрах Ст х для т ^ 16 и торах Ст х Сп для ш ^ 8. Все рекуррентные соотношения и прилагающиеся данные доступны на сайте соискателя http://flowproblem.ru в разделе о гамильтоновых циклах.

Порядки найденных рекуррентных соотношений указаны в следующей таблице. Символом «*» отмечены те соотношения, которые получены впервые в рамках реферируемой диссертационной работы.

т 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Решетка 2 4 6 14 36 66 208 '346 •1342 '2086 •8958 •13523

Цилиндр 1 2 3 •7 •12 •20 *51 •74 •246 •303 •1320 •1514 •7936 '8364

Тор *6 •28 •84 •257 •856 '2785

Так, например, рекуррентное соотношение, описывающее число циклов на цилиндре Се х ?п> имеет порядок 7 и записывается в виде

а1 = 1, Я2 = 8, аз = 86, а4 = 776, а5 = 7010, а6 = 63674, а7 = 578090, а8 = 5247824, а„ = -12ап_7 — 32ап_б — 36ап_5 — 28а„_4 + 10а„_з + 9а„_ь п > 9.

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

Полученные с высокой точностью главные члены асимптотического разложения числа циклов позволяют рассчитать значения константы связности нгп для решеток и цилиндров с фиксированным значением параметра т. Применение двух методов ускорения сходимости последовательности (ягт) дает более точное значение универсальной константы связности. Теорема 4.2 [3>т х У„] х = 1.472801 ± 0.000003. Теорема 4.3 [ет х У„] х = 1.472 799 ± 0.000 003.

Третья часть главы посвящена исследованию асимптотического поведения числа циклов на торах Ст х Сп. Исследование показало, что для четных значений 4 ^ то ^ 10 асимптотика раздваивается, а для нечетных значений 3 < ш ^ 9 она остается единой. При этом оказывается известным вид асимптотики. Результат сформулирован в виде гипотезы, проверенной и истинной для для всех 3 ^ т ^ 10. Для примера обратимся к рис. 2.

70 60 50 40 30 20 10

1п Я4(п)

100 •

Щ (п)

Я6 (п - 2)

10 20 30 40 50

(а)

(б)

РИСУНОК 2 — Асимптотические свойства числа циклов на торах: (а) Число циклов на торе 64 х С„ для п = 3,..., 50; (б) Метод отношений для числа циклов на торе Сб X Сп для п = 8,..., 50

На рис. 2(а) в логарифмическом масштабе отмечено количество циклов на торе 64 X Сп. Раздваивание асимптотики наблюдается в соответствии с теоремой 2.7. На рис. 2(6) изображен ограниченный значением п = 50 пример вычисления наибольшего по модулю корня характеристического полинома рекуррентного соотношения для числа циклов на торе С<з х С„. Наблюдаются два предела: А2 ~ 96.4 и А2 ~ 82.7 для четных и нечетных п соответственно.

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

Публикации автора по теме диссертации Статьи в рецензируемых журналах и изданиях:

1. Караваев А. М. Подсчет предгамилътоновых циклов на семействах решеточных графов. Ученые записки Петрозаводского государственного университета, 2011. №6(119). С. 97-102.

2. Караваев А. М. Количество гамшътоновых циклов на тореС^хСп-Естественные и технические науки, 2011. №6(56). С. 30-32.

Другие публикации:

3. Караваев А. М. Практическое сравнение алгоритмов типа backtrack для перечисления простых циклов в графе. Сборник научных трудов по материалам международной научно-практической конференции «Современные направления теоретический и прикладных исследований '2010». Т. 32. Одесса : Черноморье, 2010. С. 9-13.

4. Караваев А. М., Воропаев А. Н. Эффективность распараллеливания явных формул для подсчета коротких циклов в графе [электронный ресурс]. Труды международной научной конференции «Параллельные вычислительные технологии '2010». г. Уфа : Уфимский государственный авиационный технический ун-т, 2010. 1 CD-ROM. С. 486-497.

5. Караваев А. М. Возможности метода динамического программирования для подсчета числа циклов в графе : тезисы. «Научное творчество молодежи» : XIII Всероссийская научно-практическая конференция. г. Анжеро-Судженск : Томск : Из-во Том. ун-та, 2009. Ч. 1. С. 41-43.

6. Караваев А. М. Эффективность параллельной реализации.метода динамического программирования для подсчета количества простых циклов в графе. «Научное творчество молодежи» : материалы XIV всероссийской научно-практической конференции, г. Анжеро-Судженск. Томск : Из-во Том. ун-та, 2010. Ч. 1. С. 43^16.

7. Караваев А. М. Количество простых циклов на двумерной квадратной решетке. «Высокопроизводительные параллельные вычисления на кластерных системах» : материалы IX Международной конференции-семинара. Владимир : Владимирский госуниверситет, 2009. С. 202-207

8. Караваев А. М. Задача о расстановке шахматных королей. Современные проблемы гуманитарных и естественных наук : материалы II международной научно-практической конференции. М., 2010. Т. II. С. 12-16.

9. Караваев А. М. Усовершенствованный метод матрицы переноса для подсчета гамилътоновых цепей на прямоугольных решетках и цилиндрах : труды [электронный ресурс]. Сборник трудов международной научной конференции «Параллельные вычислительные технологии '2011». г. Москва : МГУ им. М. В. Ломоносова, 2011. 1 CD-ROM. С. 695.

10. Караваев А. М. Кодирование состояний в методе матрицы переноса для подсчета гамилътоновых циклов на прямоугольных решетках, цилиндрах и торах. Информационные процессы, 2011. Т. 11. №4. С. 476-499.

11. Караваев А. М., Перепечко С. Н. Подсчет гамилътоновых циклов на семействах торов Ст х Сп■ Материалы XVII международной конференции по вычислительной механике и современным прикладным программным системам (ВМСППС '2011), 25-31 мая 2011 г., Алушта. М : Изд-во МАИ-ПРИНТ, 2011. С. 243-245.

12. Караваев А. М. Усовершенствованный метод матрицы переноса для подсчета гамилътоновых циклов на прямоугольных решетках и цилиндрах. Актуальные проблемы гуманитарных и естественных наук, 2011. №4(27). С. 16-24.

13. Караваев А. М. Усовершенствованный метод матрицы переноса для подсчета гамилътоновых цепей на прямоугольных решетках и цилиндрах. Информационные процессы, 2011. Т. 11. №3. С. 336-347.

14. Караваев А. М. О подсчете гамилътоновых циклов в семействах прямоугольных решеток и цилиндров Материалы международной конференции «Математика, экономика, менеджмент: 100 лет со дня рождения Л. В. Канторовича». СПб. : ООО «ТАИС», 2012. С. 47-48.

Подписано к печати 09.02.12. Формат 60 х 84 lk .

Бумага офсетная. Гарнитура Тайме. Печать цифровая. Печ. л. 1,00.

Тираж 100 экз. Заказ 5361.

Отпечатано в Отделе оперативной полиграфии химического факультета СПбГУ 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., 26 Тел.: (812) 428-4043,428-6919

Текст научной работы диссертации и автореферата по математике, кандидата физико-математических наук, Караваев, Артем Михайлович, Петрозаводск

61 12-1/652

Петрозаводский государственный университет

На правах рукописи

Караваев Артем Михайлович

Подсчет гамильтоновых циклов на прямоугольных решетках, цилиндрах и торах методом матрицы переноса

01.01.09 — дискретная математика и математическая кибернетика

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель — кандидат физико-математических наук, доцент С. Н. Перепечко

Петрозаводск — 2012

Оглавление

Введение 4

Терминология и система обозначений 14

Вспомогательная терминология..................................14

Общая схема алгоритма..........................................17

Состояния и переходы............................................18

Список обозначений................................................22

1 Обзор литературы 24

1.1 Подсчет циклов в сеточных графах........................24

1.2 Константа связности........................................27

1.3 Вычислительные особенности

метода матрицы переноса..................................29

1.4 Особенности распараллеливания..........................33

1.5 Явные формулы

и рекуррентные соотношения..............................34

1.6 Экстраполяция числовых

последовательностей........................................38

2 Метод матрицы переноса 46

2.1 Общее описание метода......................................46

2.2 Применение метода матрицы переноса

к поставленным задачам....................................48

2.3 Примеры применения метода

к небольшим графам........................................53

2.3.1 Число циклов на решетках х Уп и У4 х Тп . . 53

2.3.2 Число циклов на цилиндрах Сз х СРП и С4 х Уп . 60

2.3.3 Число циклов на торах Сз х Сп и С4 х Сп .... 66 2.4 Выводы к главе 2............................................78

3 Кодирование состояний в задачах подсчета циклов 79

3.1 Кодирование состояний

на решетках и цилиндрах..................................80

3.1.1 Переходы между состояниями......................85

3.1.2 Метод динамического программирования .... 87

3.1.3 Методы распараллеливания........................91

3.1.4 Оптимизация ........................................97

3.2 Кодирование состояний на торах..........................99

3.2.1 Переходы между состояниями...........104

3.2.2 Метод динамического программирования .... 106

3.2.3 Количество состояний...............106

3.2.4 Оптимизация ....................109

3.3 Выводы к главе 3......................112

4 Предельные свойства в задачах подсчета циклов 113

4.1 Рекуррентные соотношения................113

4.1.1 Алгоритм вывода рекуррентных соотношений . 114

4.1.2 Результаты, полученные алгоритмом ......120

4.2 Асимптотика последовательностей............121

4.2.1 Ускорение сходимости...............124

4.3 Асимптотика для циклов на торе.............129

4.3.1 Гипотеза о виде асимптотики...........131

4.4 Выводы к главе 4......................132

Заключение 134

Список использованных источников 137

Введение

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

В работе рассматриваются три семейства графов: прямоугольные решетки Тт х цилиндры Ст х Уп и торы Ст х Сп (рис. 1).

Рисунок 1 — Примеры сеточных графов. Слева направо: решетка Т4 х цилиндр С8 х и тор Сб х

Любая решетка порождается прямым произведением двух простых цепей Угп и УТ1, первая из которых имеет т вершин, а вторая — п. Будем называть число т шириной решетки (протяженность слева направо), а п - ее длиной (протяженность снизу вверх). Символом Ст х Тп обозначается цилиндр, представляющий собой прямое произведение цикла Ст из т вершин (периметр цилиндра) и цепи Уп из тг вершин (высота, или образующая цилиндра). Тор Ст х Сп является прямым произведением двух циклов Ст и Сп.

Маршрут в графе [1] называется замкнутым, если его начальная вершина совпадает с конечной. Маршрут называется простой цепью, если все его вершины различны. Замкнутая цепь называется циклом, а простая замкнутая цепь — простым циклом. Простой цикл, проходящий через все вершины графа, называется гамилъто-новым. Поскольку работа посвящена только гамильтоновым циклам, будем для краткости называть их просто циклами, если это не порождает неоднозначной интерпретации.

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

Актуальность. В настоящее время использование систем компьютерной алгебры и высокопроизводительных вычислений является неотъемлемым атрибутом при решении сложных естественно-

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

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

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

Степень разработанности проблемы. Из обзора ранее выполненных работ следует, что задаче подсчета циклов на решетках посвящена достаточно обширная литература, в которой приводятся разнообразные попытки ее решения. Широко представлены работы как чисто математической, так и физической направленности. Тем не менее, предыдущие авторы далеко не в полной мере задействовали потенциал точных методов, основанных на использовании рекуррентных соотношений. Недостаточно внимания уделялось возможностям получения новых данных с помощью вычислительных кластеров, а также анализу эффективности распараллеливания такого класса алгоритмов. Устранение этих недостатков позволило существенно расширить набор тех графов, для которых задачу подсчета циклов можно считать решенной. В то же время, в результате исследований выяснилось, что наиболее узким местом многих методов являются проблемы, связанные с архитектурой современных кластеров.

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

Логическим завершением исследования стало обобщение результатов на случай торов. При подсчете циклов в рамках известной О(п) модели среднего поля стандартным приемом в ходе вычислений является трансформация решетки в регулярный граф (тор) путем наложения циклических граничных условий. Считается, что количество циклов в получившемся графе существенно не изменится. Чтобы оценить корректность трансформации, был получен обширный набор точных данных для числа циклов на торах. Для нескольких семейств с небольшим значением т удалось вывести явные формулы. Эти данные позволяют выявить новые особенности в асимптотике О(п) модели среднего поля, не воспроизводимые ранее известными методами.

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

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

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

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

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

1. Проанализировать и систематизировать известные результаты, выявив их достоинства и недостатки.

5. Существенно увеличить точность определения константы связности по сравнению с известными методами.

6. Проверить корректность выводов полевой О(п) модели среднего поля, предполагающей сворачивание решетки в тор с последующим сведением дискретной задачи к непрерывной.

На защиту выносятся следующие положения, являющиеся основными результатами работы.

1. Разработана эффективная схема кодирования состояний для подсчета числа гамильтоновых циклов на прямоугольных решетках Ут х Уп, цилиндрах 6m х и торах Cm х Сп, на основе которой предложен новый параллельный алгоритм.

2. Расширен набор точных значений для количества циклов на решетках, цилиндрах и торах.

5. Показано, что асимптотика количества циклов на торах Gm х Сп при fi —> оо имеет качественно иной вид, нежели на решетках ^т х и цилиндрах Cm х СРП, раздваиваясь при четном m, что свидетельствует о необходимости уточнения основных принципов проведения расчетов в рамках стандартной О(п) модели среднего поля.

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

Научная новизна диссертации состоит в том, что все выносимые на защиту положения являются новыми результатами, полученными в настоящей работе.

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

По теме исследования было опубликовано 14 научных работ: 5 научных статей [2-6], 2 из которых ([4,6]) в журналах, рекомендованных ВАК для публикации; 9 трудов и тезисов всероссийских и международных конференций [7-15]. Результаты диссертационной работы докладывались лично автором и обсуждались на международных конференциях по параллельным вычислениям «Высокопроизводительные параллельные вычисления на кластерных системах» (2009) и «Параллельные вычислительные технологии» (дважды, в 2010 и 2011 г.), на международной конференции по вычислительной механике и современным прикладным программным системам (ВМ-СППС '2011), на конференции «Математика, экономика, менеджмент: 100 лет со дня рождения Л. В. Канторовича», на научном семинаре кафедры исследования операций математико-механического факультета СПбГУ под руководством зав. каф. д. ф.-м. н., профессора Н. Н. Петрова, (дважды, в 2010 и 2011 г.), а также на научных семинарах кафедры прикладной математики и кибернетики ПетрГУ.

Диссертация состоит из введения, раздела с терминологией, четырех глав, заключения и списка источников. Общий объем диссертации составляет 145 страниц (включая библиографию из 52 источников). Работа содержит 36 иллюстраций и 21 таблицу.

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