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

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

Кузнецова Александра Сергеевна

ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ ОПТИМИЗАЦИИ НА ГРАФАХ КЭЛИ

05.13.01 — Системный анализ, управление и обработка информации (космические й информационные технологии)

АВТОРЕФЕРАТ

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

2 4 ОКТ 2013 005535539

Красноярск-2013

005535539

Работа выполнена в Сибирском государственном аэрокосмическом университете имени академика М.Ф. Решетнева, г. Красноярск

Научный руководитель:

доктор физико-математических наук, профессор Сафонов Константин Владимирович

Официальные оппоненты:

доктор технических наук, профессор Легалов Александр Иванович

Сибирский федеральный университет, заведующий кафедрой вычислительной техники

доктор физико-математических наук, профессор Шлёпкин Анатолий Константинович

Красноярский государственный аграрный университет, профессор кафедры высшей и прикладной математики

Ведущая организация:

Институт системного анализа РАН, г. Москва

Защита состоится 15 ноября 2013 г. в 14 часов на заседании диссертационного совета Д 212.249.02 при Сибирском государственном аэрокосмическом университете имени академика М.Ф. Решетнева по адресу: 660014, г. Красноярск, проспект имени газеты "Красноярский рабочий", 31.

С диссертацией можно ознакомиться в библиотеке Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева.

Автореферат разослан октября 2013 г.

Ученый секретарь диссертационного совета

Кузнецов А.А.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

В последние десятилетия теория графов Кэли развивается как отдельная большая ветвь теории графов. Графы Кэли находят применение как в математике, так и за ее пределами. Заметим, что известная задача по определению так называемого "числа Бога" кубика Рубика 3x3x3, т. е. минимального количества поворотов граней кубика за которое его можно "собрать" из любого начального положения, сводится к исследованию соответствующего графа Кэли.

Неожиданное применение графы Кэли нашли в информационных технологиях после пионерской работы 1986 года С. Эйкерса и Б. Кришнамурти, которые впервые предложили применять указанные графы для представления компьютерных сетей, в том числе для моделирования топологий многопроцессорных вычислительных систем (МВС) — суперкомпьютеров. С тех пор данное направление активно развивается. Это связано с тем, что графы Кэли имеют много привлекательных свойств, из которых выделим их регулярность, вершинно-транзитивность, малые диаметр и степень при достаточно большом количестве вершин в графе. Кстати, такие базовые топологии сети, как "кольцо" и "гиперкуб", являются графами Кэли. Среди множества работ отдельно стоит отметить статью С. Шайбелла и Р. Стаффорда 1992 года, в которой показано, что наряду с диаметром графа Кэли, очень важное значение для производительности МВС имеет также средний диаметр графа.

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

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

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

Поиск минимального слова в большой конечной группе является хотя и разрешимой, но достаточно сложной проблемой. Это связано с тем, что в общем случае задача по определению минимального слова в группе, а следовательно и диаметра графа Кэли, как показали С. Ивен и О. Голдрейх в 1981 году, является ^-трудной. Так, при вычислениии в 2010 году упомянутого выше "числа Бога", которое равно диаметру соответсвующего графа Кэли, Т. Рокики, Г. Коцем-ба, М. Дэвидсон и Д. Детридж доказали, что любая конфигурация кубика Рубика может быть решена не более чем в 20 ходов. Для установления данного факта потребовалось около 35 "процессоро-лет" распределенных вычислений. Поэтому для эффективного решения задач оптимизаци на графах Кэли, имеющих большое количество вершин, необходимо применять МВС. В связи с этим представляется актуальной проблема разработки параллельных алгоритмов для исследования графов Кэли частных классов групп.

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

Поставленная в диссертации цель достигается путем решения следующих задач.

1. Проанализировать существующие методы и алгоритмы, реализуемые на ЭВМ, для исследования свойств графов Кэли.

2. Создать базовый последовательный алгоритм А-1 для решения задач оптимизации на графах Кэли, доказать его корректность.

3. На основе А-1 разработать параллельные алгоритмы для реше-. ния задач оптимизации на графах Кэли симметрических групп, а

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

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

Соответствие диссертации паспорту специальности. Работа выполнена в соответствии с пунктом 4 — "Разработка методов и алгоритмов решения задач системного анализа, оптимизации, управления, принятия решений и обработки информации" паспорта специальности ВАК 05.13.01 — системный анализ, управление и обработка информации.

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

Научная новизна диссертационной работы

1. Создан новый последовательный алгоритм A-I для решения задач оптимизации на графах Кэли, обоснована его корректность (теорема 1).

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

3. Решены задачи оптимизации на графах Кэли симметрических групп S,i для п < 13, заданных циклами транспозиций, на основе которых определены ранее неизвестные диаметры, средние диаметры и функции роста указанных графов (теорема 2).

4. Решены задачи оптимизации на графах Кэли конечных двупо-рожденных групп периода пять Вк при к < 5 (заданных рс-представлениями), на основе которых найдены ранее неизвестные диаметры, средние диаметры и функции роста данных графов для симметричного (теорема 4), а также несимметричного (теорема 5) порождающих множеств. Для В* получены полиномы Холла (теорема 3), позволящие на порядок быстрее стандартного собирательного процесса умножать элементы из Bk■

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

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

Апробация. Результаты диссертационной работы докладывались автором на следующих международных и всероссийских конференциях: XIV, XV, XVI Международная конференция "Решетневские чтения" (Красноярск, 2010-2012 гг.); Международная алгебраическая конференция "Мальцевские чтения" (Новосибирск, 2012 г.); VII Всероссийская конференция "Всесибирский конгресс женщин математиков" (Красноярск, 2012 г.); L Международная научная студенческая конференция "Студент и научно-технический прогресс" (Новосибирск, 2012 г.); XI, XII Сибирская научная школа-семинар с международным участием "Компьютерная безопасность и криптография" — SIBECRYPT (Иркутск, 2012 г.; Томск 2013 г.).

Результаты неоднократно обсуждались на семинарах в Сибирском государственном аэрокосмическом университете и Красноярском государственном аграрном университете.

Публикации. По теме диссертации опубликовано 13 работ, среди которых 4 в журналах из перечня ВАК России, а также 2 программы для ЭВМ, прошедших государственную регистрацию.

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

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

Определение 1. Положим С? — конечная группа и X с С. Множество X = {х1,х2,... ,хт} называют порождающим множеством группы, а его элементы — порождающими, и записывают С? = (X), если любой элемент из С можно представить в виде конечного произведения из порождающих:

(? = (X) => Ур € С? д = а\ ■ а2 • • • • • где а* 6 X.

Порождающее множество X называют также алфавитом, а порождающие элементы х^ — буквами.

Определение 2. Пусть д элемент из С и д = а\- а2-... -а5, где оц € X. Правую часть данного выражения мы будем называть словом и записывать ага2.. .ая. Множество всех слов над алфавитом X будем обозначать X*.

Если необходимо подчеркнуть, что слово V е X* соответствует элементу то следует писать: ьд. Очевидно, что фиксированное

слово V соответствует только лишь одному элементу группы.

Определение 3. Положим у — произвольное слово из X". Количество букв, входящее в v, будем называть длиной слова v и обозначать 1еп^Ь(г)).

Единица группы е будет представлена пустым словом, которое мы также обозначим е. По определению 1еп§Ш(е) = 0.

На множестве порождающих введем отношение порядка "-<":

-< х2 -< ■ ■ ■ -< хт}.

В работе предполагается, что произвольные слова из X* упорядочены лексикографически.

Определение 4. Слово у будем называть минимальным в С относительно введенного порядка, если для любого другого слова и>, удовлетворяющего условию уд = юд, будет выполняться и -< и>.

Определение 5. Длиной X) элемента д в алфавите X

будем называть длину минимального слова уд € X*, представляющего данный элемент, т. е.

1еп^Ь(5,Х) = тт{1еп§Л(г>9) | уд € X*}.

Определение 6. Диаметром сНат((7, X) группы (7 относительно порождающего множества X будем называть максимальную длину элементов данной группы. Другими словами,

<Нат(С,Х) = тах{1еп^Ь(д, X) \ д 6 С},

или,

сИат(С,Х) = тах{тт{1еп^Ь(г;5) | уд е X*} | д е С?}.

Определение 7. Пусть О = (X). Шаром КГ{С1,Х) радиуса г группы С относительно X будем называть множество

Кг&Х) = {д <= в \ 1еп^Ь(5,Х) < г}.

Таким образом шар КТ(С,Х) радиуса г представляет собой все элементы группы С, длины которых относительно порождающего множества X не превышают г.

Определение 8. Функция роста X, г) группы <3 =

{X) от аргумента г е {0} и N задается соотношением ёго™Й1(С?,.Х,0) = 1 и ^отгЛ^.г) = \КГ(С,Х)\ - при

г € N.

Это означает, что каждое значение функции роста X, г)

равно числу элементов группы <3 = (X) фиксированной длины г.

Определение 9. Средним диаметром сНап^С, X) конечной группы О будем называть среднюю длину ее элементов в алфавите X. Другими словами:

_ Е £ &отгЛЪ(С,Х,г)-г

аЕЕ«?,*, . -. ---.

Определение 10. Графом Г = (У,Е) называют совокупность двух множеств — множества вершин V = {г^,^,..., г>т} и множество ребер Е = {ех, е2,..., еп}, где каждое ребро из Е определяется неупорядоченной парой вершин

Отметим, что приведенная выше формулировка определяет неориентированный граф. Если же каждое ребро графа задается упорядоченной парой (и^и,-) вершин, то такой граф называют ориентированным.

Далее под графом будем понимать неориентированный граф.

Пусть В] и »2 - вершины графа, е\ — соединяющее их ребро. Тогда вершина VI и ребро е\ инцидентны, ребро ех и вершина г;2 также инцедентны. Два ребра, инцидентные одной вершине, называются смежными', две вершины, инцидентные одному ребру, также называются смежными.

Порядок графа определяется числом его вершин |У|.

Определение 11. Автоморфизмом графа Г = (У, Е) называется отображение <р множества вершин на себя, сохраняющее смежность, т. е. если {ы, и} е Е, то будет верно {(р(и),1р(у)} 6 Е.

Определение 12. Граф Г = (У,Е) называют вершинно-транзитивным, если для любых двух вершин и,у Е V существует автоморфизм <р, при котором <р(и) = у.

Определение 13. Маршрутом в графе Г = (V, Е) называют последовательность вершин и ребер из Г

"¿1! ^¿1) 1 £¿2 ) ■ ■ • ; е«р I ^¿р+1 >

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

Определение 14. Расстоянием й{и, у) между вершинами и и V в графе Г будем называть длину кратчайшей цепи, связывающей эти две вершины.

Определение 15. Диаметром <Нагп(Г) графа Г называется расстояние между двумя наиболее удаленными вершинами в графе, т. е.

сИат(Г) = таг>) | и, V € V}.

Определение 16. Средним диаметром сНат(Г) конечного непустого графа Г = (V, Е) будем называть среднее расстояние между его вершинами. Другими словами:

Е <1{и,ь)

сПат(Г) = ^

Графы Кэли

Определение 17. Пусть X — порождающее множество группы С, т. е. й = (X). Графом Кэли Г = Сау(С,Х) = (У, Е) называют ориентированный граф, обладающий следующими свойствами:

СО множество вершин У(Г) соответствуют элементам группы О,

(И) множество ребер Е(Г) состоит из всех упорядоченных пар (в> хд), где д е С и х е X.

В дальнейшем будем считать порождающее множество X симметричным и свободным от единичного элемента группы, т. е. х € X =>■ х6 X и е ф. X. Поскольку X является свободным от единичного элемента, то граф Г не содержит петель. Симметричность порождающего множества означает, что граф будет неориентированным и без кратных ребер, т. е. если в графе имеется ребро из д в хд, то оно совпадает с ребром из хд в х~1(хд) = д.

Следующая лемма определяет базовые свойства графа Кэли и показывает взаимосвязь между графом и порождающей его группой.

Лемма. Пусть С? = (X) и Г = Сау(С, X) — граф Кэли группы С относительно X. Тогда

(г) Г является связным \Х¡-регулярным графом,

(и) Г является вершинно-транзитивным графом,

(Иг) Уд,Н е в й(д,К) = 1еп^Ь(/г5-\Х),

(ги) (Пат (Г) =

(и) <Пат(Г) = &ат(С, X).

Беря во внимание свойства (и) и (Ш) вышеприведенной леммы, мы можем определить функцию роста графа Кэли growth(Г, г) = X, г), которая задает количество вершин в графе, удаленных от любой заданной вершины на расстояние г.

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

Алгоритм A-I

Вход: G = (G, ■) — конечная группа и X = {xi х2 -< ... -< хт} — упорядоченное порождающее множество G.

Выход: диаметр diam(r), средний диаметр diam(r) графа Кэли Г = Cay(G,X), а также функция роста графа growth(r) = growth(r,r), О < г < diam(r).

1. s = О, Кв = K„(G,X) = {е} - шар группы G, Т = Ка,

2. s = s+1, К3 = К8-1, U = xi-TUx2-T. ..Uxm-T — лексикографически упорядоченное множество.

3. Т = 0, г = 1.

4. Если щ <£ Кд, то Кэ = Ks U щ, Т = Т U щ.

5 Если < то ^ = ^ + 1' переход в пункт 4;

[г = |С/|, то переход в пункт 6.

„ _ ГТ Ф 0, то переход в пункт 2;

6. Если <

I Т = 0, то переход в пункт 7.

7. diam(r) = s - 1, growth(r) = |7fr| — l-R^-il для 1 < г < s-1 и

s— 1

growth(r) • г

growth(O) = 1, diam(r) = ————:-. Возврат значений.

l-fts-ll

Доказана следующая

Теорема 1. Алгоритм A-I корректен, т. е. для любой конечной группы он за конечное число шагов находит характеристики соответствующего графа Кэли.

В главе 2 настоящей работы показана модифицированная версия алгоритма A-I, адаптированная к изучению графов Кэли симметрических групп на МВС. После чего исследуются графы симметрических групп, заданных циклами из транспозиций.

Рассмотрим семейство графов, каждого представителя которого называют "modofied bubble-sort graph" или в переводе на русский "модифицированный граф пузырьковой сортировки". Указанные графы, также как и графы пузырьковой сортировки, задаются симметрическими группами Sn, однако множество транспозиций, порождающих группу графа, теперь образует цикл:

Sn = (Х„), где Хп = {(гг + 1) | г = 1,2,...,п- 1} U {(1 п)}.

На сегодняшний день остается открытым вопрос о значениях таких важных характеристик графов Кэли Сау{Бп,Хп) как диаметр и средний диаметр.

В связи с тем, что порядки групп 5„ при п > 10 достаточно большие, для изучения свойств графов Кэли указанных групп необходимо применять МВС.

Для увеличения скорости вычислений описанный в главе 1 алгоритм А-1 можно распараллелить следующим образом. Множество К3(Зп,Х„) разбивается на т = п(п — 1)(п — 2)... (п — к +1) непересекающихся классов элементов (подстановок):

771

К3 = К П К5 = 0 при г ± 3-

г=1

Каждый класс К{ будет однозначно определяться фиксированным набором значений (н,г2,...,гк), т- е.

'1 2 ... к ... п'

VдеК=>д =

\гг г2 ... 1к ■■■ г,

Аналогичным образом массив и при каждом з также делится на т непересекающихся классов элементов и дальнейшая обработка данных для каждой пары множеств [Д и К (пункты 4-5 алгоритма А-1) производится независимо. Нетрудно заметить, что рассмотренное разделение массивов не влияет на корректность работы алгоритма. Параметр к определяется экспериментально и зависит от характеристик МВС. Указанная процедура, как показали реальные расчеты, дает ощутимый прирост скорости вычислений.

Решение задач оптимизации на указанных графах Кэли дало возможность доказать приведенную ниже теорему.

Теорема 2. Пусть симметрическая группа Зп задана множеством трансопозиций Хп = {(г г + 1) | г = 1,2,..., п — 1} и {(1 п)} и Гп = Сау(Зп,Хп) — соответствующий Бп граф Кэли, тогда для п < 13 верны следующие утверждения:

(г) г) заданы таблицами 2.1-2.12 из диссертации,

(И) сИат(Гп)

4.

п2 - п + 1

(Иг) с!1ат(Г„) =

В третьей главе представлена модификация алгоритма A-I, адаптированная к исследованию на МВС, графов Кэли групп, заданных рс-представлениями. Затем приведен алгоритм для быстрого умножения элементов в двупорожденных группах периода пять Вк (заданных рс-представлениями), основанный на полиномах Холла. После чего исследуются графы Вк, порожденных симметричным и несимметричным множествами.

Пусть Вк = Bq(2,5, к) — максимальная конечная двупорожденная группа периода 5 ступени нильпотентности к. В данном классе групп наибольшей является группа Bi2, порядок которой равен 534.

Обычно Вк задают при помощи так называемого рс-представления {power commutator presentation), которое несложно получить, используя систему компьютерной алгебры GAP. В этом случае каждый элемент группы задается в виде произведения упорядоченной последовательности специальных элементов группы (базисных коммутаторов) a-i, а2,..., ап в некоторых степенях, принимающих значения из поля Галуа Z5:

УдеВк^ д = а? ...ахп», Xi 6 Z5.

Положим X = {ai, 02} — порождающие элементы Вк. В настоящей главе исследованы свойства ориентированных графов Кэли групп Вк при к < 5 относительно X, а также неориентированных графов относительно симметричного порождающего множества У = {a\,ai1,a2,a21}.

Поскольку порядки групп Вк при к > 3 достаточно большие, для изучения свойств графов Кэли указанных групп целесообразно применять МВС. Поэтому алгоритм A-I необходимо адаптировать к использованию на суперкомпьютере.

Распараллелим алгоритм A-I следующим образом. Разделим множество Ks(Bk,X) или Ks{Bk,Y) на гп = 5е непересекающихся классов элементов, где каждый класс К{ будет однозначно определяться фиксированным набором значений (71,72, ■ ■ • ,7с), т. е.

ЧдеК{=>д = а?а? ...а%° ахс%

Аналогичным образом массив U при каждом $ также делится на т непересекающихся классов элементов и дальнейшая обработка данных для каждой пары множеств Щ и К{ (пункты 4-5 алгоритма A-I) производится независимо. Понятно, что такое разделение массивов не оказывает влияния на корректность работы алгоритма. Параметр с определяется экспериментально и зависит от характеристик МВС.

Данная модификация алгоритма A-I, как показывают эксперименты на МВС, дает существенный прирост скорости вычислений.

При нахождении функции роста группы очень часто требуется вычислять произведения ее элементов (пункт 2 алгоритма A-I). Как было сказано, порядки групп В* при к > 3 достаточно большие, поэтому итоговое время расчета во многом будет зависеть от того, насколько быстро мы сможем умножать элементы в группе.

Пусть а*1... а£п и af ... ay¿ — два произвольных элемента из В Тогда их произведение равно

в?...<£■•о?...о£« = а? ...а*

Основой для нахождения коэффициентов Zi является собирательный процесс, который реализован в системах компьютерной алгебры GAP и MAGMA. Однако это не единственный способ для вычисления произведений элементов группы. Ф. Холл показал, что z¡ представляют собой полиномиальные функции (в нашем случае над полем Z5), зависящие от переменных жх,..., x¡, yi,..., уи которые называют сейчас полиномами Холла. Согласно Холлу:

Zi = Xi + Vi + Pi(x 1,..., Xj_i, 2/1,..., yi-1).

4. Симе анонсировал, что вычислил указанные полиномиальные функции, однако они так и не были нигде опубликованы. Кроме того не удалось найти компьютерные программы, в которых был бы реализован метод полиномов Холла для вычисления произведений элементов группы. Для восполнения указанного пробела в диссертации приведено подробное описание алгоритма для вычисления полиномов Холла в группах В¡¡. Полиномы были найдены при помощи машинных вычислений в системе компьютерной алгебры MATLAB, после чего полученные формулы реализованы в виде отдельной программы на языке Си. Сравнив скорость вычислений около 104 произведений случайно выбранных элементов в каждой из групп В^, было отмечено, что метод полиномов Холла имеет значительное преимущество перед собирательным процессом. В среднем, использование полиномов позволяет получить произведение двух элементов группы на порядок (т. е. в 10 раз) быстрее собирательного процесса.

Теорема 3. Пусть а*1... а*" и af ... оьпп — два произвольных элемента из £?ь где к £ N и к < 12. Тогда их произведение равно af1... а*" ■ af ... а^р = af ... а*", где z¡ 6 Z5 — полиномы Холла, задаваемые формулами (*) из приложения диссертации.

Указанные полиномы занимают более 40 страниц текста, формулы (1)-(8) иллюстрируют только первые 8 из 34.

поэтому

21 =£1+2/1, (1)

22 = х2 + 2/2, (2)

2з = хз + 2/з + а;22/1, (3)

г4 = х4 + ул+ х2 ^ ^ + хзУи (4)

25 = хь + 2/5 + Х2У1У2 + У1 + х3у2, (5)

¿6 = а^б + 2/6 + Х2 ) + х3 Р ) + хщъ (6)

27 = х7 + 2/7 + .т2 2/2 + 22) ( 21) + ХзУ1г/2 + хт + ХьШ'

г8 = а* -I 2/8 + х22/1 ^ + 2/12/2 + ( ^ 2/1 + (+ ^2/2- (8)

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

Теорема 4. Пусть группа В& задана порождающим множеством У и Гк — Сау(Вь,У) — соответствующий Вк граф Кэли, тогда для к < 5 верны следующие утверждения:

(г) 5гош);}1(Г&, г) заданы таблицами 3.1-3.5 из диссертации; (И) (Иат(Г1) = 4, Н1ат(Г1) = ~ = 2,4;

(Ш) (Иат(Г2) = 6, <Иат(Г2) = -г- « 3,6;

5Л

__21й7П

(т) сИат(Гз) = 10, а1ат(Г3) = « б, 9;

55

(и) Шат(Г4) = 19, = 4893016 » 12,5;

5®

(ш) сНат(Г5) = 20, НЙЫ(Г5) = « 15,4.

Теорема 5. Пусть группа Вь задана порождающим множеством X и Ifc = Сау(Вк,Х) — соответствующий B¡¿ ориентированный граф Кэли, тогда для к < 5 верны следующие утверждения:

(г) growth(fí:,r') заданы таблицами 3.6-3.10 из диссертации;

(и) diam(fi) = 8, diam(fi) = ^ = 4;

___ 745

(iii) diam(r2) = 10, diam(r2) = — «¡ 6,0;

о-5

(iv) diam(f3) = 20, dîâm(f3) = —-»11,5;

5й

(v) diam(f4) = 30, düS(f4) = 766г°я195 и 19,6;

5°

(vi) diam(fs) = 32, düS(f5) = 234^J415 « 24,0.

5 u

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

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

Работа выполнена при частичной финансовой поддержке проекта "Компьютерное моделирование сложных алгебраических систем" по заказу Минобрнауки РФ, № госрегистрации 1.3755.2011.

Автор сердечно благодарит своего научного руководителя — профессора К.В Сафонова за всестороннюю поддержку, полученную во время написания диссертации.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации в журналах из перечня ВАК России

[1] Кузнецова A.C., Кузнецов A.A. Компьютерное моделирование конечных двупорожденных групп периода 5 // Вестник СибГАУ. 2012. № 5(45). С. 59-62.

[2] Кузнецова A.C., Кузнецов A.A. О взаимосвязи функций роста в симметрических группах с задачами комбинаторной оптимизации // Вестник СибГАУ. 2012. № 6(46). С. 93 -97.

[3] Кузнецова A.C., Кузнецов A.A. Быстрое умножение элементов в конечных двупорожденных группах периода пять // Прикладная дискретная математика. 2013. № 1(18). С. 110-116.

[4] Кузнецова A.C. Исследование функций роста в конечных двупорожденных группах периода 5 // Вестник СибГАУ. 2013. № 3(49).

Прочие публикации

[5] Кузнецова A.C., Кузнецов A.A. Теоретико-групповой подход в задачах комбинаторной оптимизации // Труды XIV Международной конф. "Решетневские чтения". Красноярск: Изд-во СибГАУ, 2010. С. 449.

[6] Кузнецова A.C., Кузнецов A.A. Моделирование топологии мультипроцессорной вычислительной системы на основе теории групп // Труды XVI Международной конф. "Решетневские чтения". Красноярск: Изд-во СибГАУ, 2012. С. 545-546.

[7] Кузнецова A.C., Кузнецов A.A. Быстрое умножение элементов в двупорожденных бернсайдовых группах периода пять // Материалы VII Всероссийской конф. "Всесибирский конгресс женщин математиков". Красноярск: Изд-во СибГТУ, 2012. С. 108-110.

[8] Кузнецова A.C., Сафонов K.B. Об одной задаче комбинаторной оптимизации // Приложение к журналу Прикладная дискретная математика. 2012. № 5(17). С. 15-16.

[9] Кузнецова A.C., Кузнецов A.A. К вопросу о вычислении функции роста в бернсайдовой группе Ва(2,5,7) // Тезисы Международной конф. "Мальцевские чтения". Новосибирск: Изд-во ИМ СО РАН, 2012. С. 62.

[10] Кузнецова A.C., Кузнецов A.A. Функции роста в конечных дву-порожденных бернсайдовых группах периода 5 // Материалы юбилейной 50-й Международной научной студенческой конф. "Студент и научно-технический прогресс": Математика. Новосибирск: Изд-во НГУ, 2012. С. 12.

[11] Кузнецова A.C., Кузнецов A.A., Сафонов К.В. Параллельный алгоритм вычисления функций роста в конечных двупорожденных группах периода 5 // Приложение к журналу Прикладная дискретная математика. 2013. № 6. С. 119-121.

Разработки, зарегистрированные в государственном объединенном фонде электроннных ресурсов "Наука и образование"

[12] Кузнецова A.C., Кузнецов A.A. Вычисление функций роста в симметрических группах // Свидетельство о государственной регистрации электронного ресурса № 18544 от 27.09.2012.

[13] Кузнецова A.C., Кузнецов A.A. Вычисление функций роста в конечных полициклических группах // Свидетельство о государственной регистрации электронного ресурса № 18555 от 03.10.2012.

Кузнецова Александра Сергеевна

Параллельные алгоритмы оптимизации на графах Кэли

Автореферат

Подписано в печать 07.10.2013. Формат 60x84/16. Уч.-изд. л. 1,0. Тираж 100 экз. Заказ №

Отпечатано в отделе копировально-множительной техники СибГАУ 660014, г. Красноярск, пр. им. газ. "Красноярский рабочий", 31.

СИБИРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ УНИВЕРСИТЕТ ИМЕНИ АКАДЕМИКА М.Ф. РЕШЕТНЕВА

04201364383 На пРавах РУК0ПИС^^

КУЗНЕЦОВА АЛЕКСАНДРА СЕРГЕЕВНА

УДК 519.176

ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ ОПТИМИЗАЦИИ НА ГРАФАХ КЭЛИ

05.13.01 — Системный анализ, управление и обработка информации (космические и информационные технологии)

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

Научный руководитель:

доктор физико-математических наук, профессор Сафонов К.В.

Красноярск-2013

Содержание

Введение 3

1 Основные определения и понятия 9

1.1. Группы ..............................................................................9

1.1.1. Симметрическая группа ..............................................14

1.2. Графы..............................................................................15

1.2.1. Графы Кэли................................................................17

1.3. Последовательный алгоритм А-1................................................18

1.3.1. Примеры ..................................................................22

2 Исследование графов симметрических групп 26

2.1. Постановка задачи................................................................26

2.2. Параллельная версия алгоритма А-1 для графов групп Бп..................27

2.3. Анализ компьютерных вычислений ............................................28

3 Исследование графов конечных двупорожденных групп периода 5 38

3.1. Постановка задачи................................................................38

3.2. Быстрое произведение элементов группы......................................39

3.3. Параллельная версия алгоритма А-1 для графов групп ..................48

3.4. Изучение графов для симметричного порождающего множества............49

3.5. Изучение графов для несимметричного порождающего множества .... 52

Заключение 58

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

Работы автора по теме диссертации 67

Приложение 70

Введение

Актуальность темы. Определение графа Кэли было дано известным английским математиком Артуром Кэли в 1878 году для представления алгебраической группы, заданной фиксированным множеством порождающих элементов [11].

В последние десятилетия теория графов Кэли развивается как отдельная большая ветвь теории графов. Графы Кэли находят применение как в математике, так и за ее пределами [42]. Заметим, что известная задача по определению так называемого "числа Бога" кубика Рубика 3 х 3 х 3, т. е. минимального количества поворотов граней кубика за которое его можно "собрать" из любого начального положения, сводится к исследованию соответствующего графа Кэли [44].

Неожиданное применение графы Кэли нашли в информационных технологиях после пионерской работы 1986 года С. Эйкерса и Б. Криш-намурти [25], которые впервые предложили применять указанные графы для представления компьютерных сетей, в том числе для моделирования топологий многопроцессорных вычислительных систем (МВС) — суперкомпьютеров [1,4,14,24]. С тех пор данное направление активно развивается. Это связано с тем, что графы Кэли имеют много привлекательных свойств, из которых выделим их регулярность, вершинно-транзитивность, малые диаметр и степень при достаточно большом количестве вершин в графе. Кстати, такие базовые топологии сети, как

"кольцо" и "гиперкуб" [2], являются графами Кэли. Среди множества работ [11,26-31,33,35,39-41,43,45-47,51,52,56,57] отдельно стоит отметить статью С. Шайбелла и Р. Стаффорда 1992 года [52], в которой показано, что наряду с диаметром графа Кэли, очень важное значение для производительности МВС имеет также средний диаметр графа.

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

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

Поиск минимального слова в большой конечной группе является хотя и разрешимой, но достаточно сложной проблемой. Это связано с тем, что в общем случае задача по определению минимального слова в группе, а следовательно и диаметра графа Кэли, как показали С. Ивен и О. Голдрейх в 1981 году, является ИР-трудной [32]. Так, при вы-числениии в 2010 году упомянутого выше "числа Бога", которое равно

диаметру соответсвующего графа Кэли, Т. Рокики, Г. Коцемба, М. Дэвидсон и Д. Детридж доказали, что любая конфигурация кубика Рубика может быть решена не более чем в 20 ходов [36]. Для установления данного факта потребовалось около 35 "процессоро-лет" распределенных вычислений. Поэтому для эффективного решения задач оптимизаци на графах Кэли, имеющих большое количество вершин, необходимо применять МВС. В связи с этим представляется актуальной проблема разработки параллельных алгоритмов для исследования графов Кэли частных классов групп.

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

Поставленная в диссертации цель достигается путем решения следующих задач.

1. Проанализировать существующие методы и алгоритмы, реализуемые на ЭВМ, для исследования свойств графов Кэли.

2. Создать базовый последовательный алгоритм А-1 для решения задач оптимизации на графах Кэли, доказать его корректность.

3. На основе А-1 разработать параллельные алгоритмы для решения задач оптимизации на графах Кэли симметрических групп, а также групп, заданных коммутаторами, т. е. рс-представлениями.

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

Соответствие диссертации паспорту специальности. Работа выполнена в соответствии с пунктом 4 — "Разработка методов и алгорит-

мов решения задач системного анализа, оптимизации, управления, принятия решений и обработки информации" паспорта специальности ВАК 05.13.01 — системный анализ, управление и обработка информации.

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

Научная новизна диссертационной работы

1. Создан новый последовательный алгоритм А-1 для решения задач оптимизации на графах Кэли, обоснована его корректность (теорема 1).

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

3. Решены задачи оптимизации на графах Кэли симметрических групп 5П для п < 13, заданных циклами транспозиций, на основе которых определены ранее неизвестные диаметры, средние диаметры и функции роста указанных графов (теорема 2).

4. Решены задачи оптимизации на графах Кэли конечных двупо-рожденных групп периода пять Вк при к < 5 (заданных рс-представлениями), на основе которых найдены ранее неизвестные диаметры, средние диаметры и функции роста данных графов для симметричного (теорема 4), а также несимметричного (теорема 5)

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

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

Апробация. Результаты диссертационной работы докладывались автором на следующих международных и всероссийских конференциях: XIV, XV, XVI Международная конференция "Решетневские чтения" (Красноярск, 2010-2012 гг.); Международная алгебраическая конференция "Мальцевские чтения" (Новосибирск, 2012 г.); VII Всероссийская конференция "Всесибирский конгресс женщин математиков" (Красноярск, 2012 г.); Ь Международная научная студенческая конференция "Студент и научно-технический прогресс" (Новосибирск, 2012 г.); XI, XII Сибирская научная школа-семинар с международным участием "Компьютерная безопасность и криптография" — 51ВЕС1^УРТ (Иркутск, 2012 г.; Томск 2013 г.).

Результаты неоднократно обсуждались на семинарах в Сибирском государственном аэрокосмическом университете и Красноярском государственном аграрном университете.

Публикации. По теме диссертации опубликовано 13 работ, среди

которых 4 в журналах из перечня ВАК России, а также 2 программы для ЭВМ, прошедших государственную регистрацию.

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

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

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

В главе 2 настоящей работы показана модифицированная версия алгоритма А-1, адаптированная к исследованию графов Кэли симметрических групп на МВС. После чего исследуются графы симметрических групп, заданных специальным множеством порождающих элементов (циклами из транспозиций).

В третьей главе представлена модификация алгоритма А-1, адаптированная к исследованию графов Кэли двупорожденных групп периода пять на МВС. Затем приведен алгоритм для быстрого умножения элементов в указанных группах, основанный на полиномах Холла. После чего исследуются графы этих групп, заданных симметричным и несимметричным множествами.

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

В приложениии приведены полиномы Холла для быстрого умножения элементов двупорожденных групп периода пять.

Глава 1

Основные определения и понятия

В настоящей главе приведены основные понятия из теории групп [3,6,13,42,53,54] и теории графов [9,15,17,22,23]. После чего дано описание нового последовательного алгоритма А-1 для вычисления функции роста, диаметра и среднего диаметра графа Кэли произвольной конечной группы. Затем доказана корректность представленного алгоритма, а в конце главы приведены примеры, иллюстрирующие его работу.

1.1. Группы

Определение 1. Пусть У — произвольное множество. Бинарной алгебраической операцией (или законом композиции) на У называют произвольное фиксированное отображение г : У х У —>■ У декартова квадрата У2 = У х У в У.

Это значит, что любой упорядоченной паре (а, Ь) элементов а, Ъ € У ставится в соответствие однозначно определенный элемент т(а, Ь) из того же множества У. Часто бинарную операцию г на У обозначают каким-нибудь специальным символом (*,-, + и т. д.) и пишут атЪ. Будем называть а-Ь (или просто аЬ) — произведением (умножением), а а + Ъ —

суммой элементов а, Ь Е У. Очевидно, что эти названия в большинстве случаев условны.

На У можно задать несколько операций. Если необходимо веди-лить одну из них, то используют скобки: (У, •), и говорят, что операция • определяет на У алгебраическую систему.

Определение 2. Группой С? = (С7, •) называется множество элементов на котором задана бинарная операция удовлетворяющая следующим условиям:

(7) для всех а,Ь,с £ (7 верно а • (Ь • с) = (а • Ъ) • с (ассоциативность);

(и) в й существует единственный единичный элемент е, такой что д • е — е • д — д для любого д 6 С;

(Ш) каждый элемент д £ С имеет обратный д~1:

9 • д"1 = д~1 • 9 = е.

Если для любых элементов а, Ь € С? выполняется а • 6 = Ь • а, то такую группу называют коммутативной или абелевой.

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

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

Приведем несколько элементарных примеров. Например, целые числа 2, рациональные действительные Е и комплексные С являются абелевыми группами относительно операции сложения чисел: (2,+),

(С,+). Ненулевые рациональные О])*, действительные М* и комплексные С* образуют коммутативные группы относительно операции умножения чисел: (О*,*), (К*,*), (О*,*)- Очевидно, что все указанные группы бесконечны.

Определение 3. Положим (7 — конечная группа и X с С. Множество X = {х1,х2, ■ ■. ,хт} называют порождающим множеством группы, а его элементы — порождающими, и записывают (2 = (X), если любой элемент из С можно представить в виде конечного произведения из порождающих:

С = (X) \/д € (7 => д = а\ • а2 •... • а8, где щ Е X.

Порождающее множество X называют также алфавитом, а порождающие элементы Хг — буквами.

Определение 4. Пусть д элемент из <2 и д = а\ • а2 • ... • а8, где ос{ е X. Правую часть данного выражения мы будем называть словом и записывать а\а2.. .а3. Множество всех слов над алфавитом X будем обозначать X*.

Если необходимо подчеркнуть, что слово V € X* соответствует элементу д е (3, то следует писать: уд.

Очевидно, что фиксированное слово у соответствует только лишь одному элементу группы.

Определение 5. Если два различных слова у = а\а2.. .аг и ту — ¡3г(32. • -А» представляют один элемент д группы (2, т. е. д = а\ ■ а2 ■ ... • аг и д = (3\- ¡32 -... • рг, то выражение а\ • а2 •... • аг = /3\ • /32 • •.. • (Зг (или уд = и)д) называют соотношением в <2.

Часто при задании группы соотношения записывают в каноническом виде: v = е. Если д = h — соотношение в группе, то в каноническом виде оно будет выглядеть д • h~l = е.

Определение 6. Положим v — произвольное слово из X*. Количество букв, входящее в v, будем называть длиной слова v и обозначать length (и).

Единица группы е будет представлена пустым словом, которое мы также обозначим е. По определению length(e) = 0.

На множестве порождающих введем отношение порядка "-<":

{Xi -<Х2<----< хт}.

Определение 7. Пусть v и w произвольные слова из X*. Будем говорить, что слово v = ai«2- • меньше слова w = fiifa.. ф3 и записывать v -< w, если имеет место одно из следующих утверждений:

(i) г < s;

(it) если г = s, тогда а\ = /?ь се2 = Pi, ■ • ■, otk-1 = Pk-ъ ®k ~< Pk для некоторого 1 < k < s.

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

Определение 8. Слово v будем называть минимальным в G относительно введенного порядка, если для любого другого слова w, удовлетворяющего условию vg = wg, будет выполняться v -< w.

Определение 9. Длиной length^, X) элемента g в алфавите X будем называть длину минимального слова vg е X*, представляющего данный элемент, т. е.

1ещ1Ъ.(д, X) = тт^ех^Цг^) | уд €= X*}.

Определение 10. Диаметром сНат(С?, X) группы С относительно порождающего множества X будем называть максимальную длину элементов данной группы. Другими словами,

сНат((2, X) = тах{1е1^]1(д, X) | д €

или,

сНат(С?,Х) = тах{т1п{1еп^Ь(г;р) | уд £ X*} | д € С?}. (1.1)

Определение 11. Пусть й = {X). Шаром КГ(С,Х) радиуса г группы С относительно X будем называть множество

Кг(в,Х) = {дев 11е^%,Х) < г}. (1.2)

Таким образом шар КГ(С,Х) радиуса г представляет собой все элементы группы С, длины которых относительно порождающего множества X не превышают г.

Определение 12. Функция роста growth(G!, X, г) группы С? = (X) от аргумента г € {0} и N задается соотношением growth(G!, X, 0) = 1 и growth((x, х, г) = \Кг(в,Х)\- \КГ^{С,Х)\ при г € N.

Это означает, что каждое значение функции роста growth(Gr, X, г) равно числу элементов группы С? = (X) фиксированной длины г.

Определение 13. Средним диаметром сИат(С?, X) конечной группы С будем называть среднюю длину ее элементов в алфавите X. Другими словами:

сИат

Е 1еп^Ь(р, X) £ growth(Gí, X, г) • г X) = '-^—щ-= —-щ-• (1-3)

1.1.1. Симметрическая группа Sn

Пусть Q — конечное множество из п элементов. Поскольку при