A parallel algorithm for computation of growth functions in the finite two-generator groups of period 5.pdf Пусть р — простое число, G — конечная группа экспоненты р. Это значит, что gp = e для всех g Е G. Так как G нильпотентна, то можно найти цепочку подгрупп G = G\ D D G2 D ... D Gn D Gn+i = e, в которой Gi нормальны в G, а факторы Gi/G+ имеют порядок р и лежат в центре G/Gi+\. Пусть для 1 ^ i ^ n элемент ai Е Gi, но ai Е Gi+\, тогда каждый элемент группы g Е G можно однозначным образом записать в виде (1) g = ai1 aY ... аПП, 0 ^ y < р. Такое представление элементов группы (рс-представление) можно получить при помощи алгоритма, известного как p-quotient algorithm [1]. Он реализован в системах компьютерной алгебры GAP и Magma. Если A — порождающее множество группы G, то любой её элемент, записанный в виде слова a1a2 ... as, где a Е A, можно преобразовать к виду (1) a1a2 ... as —a]1 a222 ... a^". (2) Процедура (2) даёт возможность решить проблему равенства слов в G. Для вычисления функции роста и диаметра Кэли группы G относительно A необходимо перечислить все элементы группы в формате минимальных слов [2]. Вычислив количество слов на каждой длине, можно получить функцию роста группы, а максимально возможная длина минимальных слов является диаметром Кэли группы. Обозначим через Ks(G) множество всех минимальных слов группы G, не превосходящих по длине s; множество Qs(G) —элементы Ks(G), записанные в виде правой части (2). Пусть s0 Е N — минимальное число, для которого выполняется Ks0(G) = Ks0+1(G). В этом случае s0 — диаметр Кэли группы G. Опишем последовательный алгоритм, вычисляющий функцию роста группы G относительно A = {a1, a2,... , am}: 1) s = 0, Ko = {e}, Qo = {a?a° ... a£}, T = Ko. 2) s = s + 1, Ks = Ks-1, Qs = Qs-1, V = a1T U a2T... U amT, T = 0, i =1. 3) Для Vi Е V Vi —— ; Если Vi Е Qs, то Ks = KsU{Vi}, Qs = QsU{Vi}, T = TU{Vi}. 4) Если i < |V|, то i = i + 1, переход в п. 3, иначе — в п. 5. 5) Если T = 0, то переход в п. 2; иначе — в п. 6. 6) Диаметр G равен s — 1, Ks-1 (G) —множество всех минимальных слов группы. Функция роста задаётся формулой f (j) = |Kj(G)| — |Kj-1(G)|, 1 ^ j ^ s — 1. Завершение работы алгоритма. Для увеличения скорости вычислений алгоритм можно распараллелить следующим образом. Множество Qs разбивается на pr непересекающихся классов элементов, где каждый класс однозначно определяется фиксированным набором значений Y1, y2 ,... , Yr. Параметр r определяется экспериментально и зависит от характеристик мультипроцессорной вычислительной системы. Пусть Bo(2,5,k) —максимальная конечная двупорождённая бернсайдова группа периода 5 ступени нильпотентности k. В данном классе групп наибольшей является группа B0(2, 5,12), порядок которой равен 534. Для каждой из B0(2, 5, k) известны рс-представления, которые несложно получить, используя систему компьютерной алгебры GAP. Положим A = {a1,a2} — порождающие элементы B0(2,5,k). Для k ^ 6 к настоящему времени вычислены функции роста и диаметры Кэли групп B0(2, 5, k) относительно A. Отметим, что для нахождения функций роста при k ^ 2 использовались компьютерные вычисления. В таблице приведены значения порядков групп B0(2, 5, k), а также их диаметры D^(A) относительно A. k |Bo(2, 5,k)| Dk (A) k |Bo(2, 5, k)| Dk (A) 1 52 8 4 58 30 2 53 10 5 510 32 3 55 20 6 514 45 Следующий нерешённый случай — k = 7. Поскольку B0(2, 5, 7) имеет достаточно большой порядок (он равен 518), для нахождения диаметра данной группы необходимо применять суперкомпьютерные вычисления. В настоящее время идет работа по программной реализации параллельной версии алгоритма на языке С+—Н с использованием интерфейса передачи данных MPI. Вычисления будут проводиться на суперкомпьютере Сибирского федерального университета.

Скачать электронную версию публикации