Алгоритм Шрайера – Симса - Schreier–Sims algorithm

В Алгоритм Шрайера – Симса является алгоритм в вычислительная теория групп, названный в честь математиков Отто Шрайер и Чарльз Симс. Этот алгоритм может найти порядок конечной группы перестановок, проверка принадлежности (содержится ли данная перестановка в группе?) и многие другие задачи за полиномиальное время. Он был представлен Sims в 1970 году на основе Лемма Шрайера о подгруппах. Сроки были впоследствии улучшены Дональд Кнут в 1991 году. Позже, еще более быстрый рандомизированный разработана версия алгоритма.

Предпосылки и сроки

Алгоритм является эффективным методом вычисления основание и мощная генераторная установка (BSGS) группа перестановок. В частности, SGS определяет порядок группы и упрощает проверку членства в группе. Поскольку SGS важен для многих алгоритмов вычислительной теории групп, системы компьютерной алгебры обычно полагаются на алгоритм Шрайера – Симса для эффективных вычислений в группах.

Время работы Schreier – Sims зависит от реализации. Позволять ${ Displaystyle G leq S_ {п}}$ быть предоставленным ${ displaystyle t}$ генераторы. Для детерминированный версии алгоритма, возможные времена работы:

${ Displaystyle О (п ^ {2} log ^ {3} | G | + tn log | G |)}$ требует памяти ${ Displaystyle О (п ^ {2} журнал | G | + tn)}$
${ Displaystyle О (п ^ {3} log ^ {3} | G | + tn ^ {2} log | G |)}$ требуется память ${ Displaystyle О (п журнал ^ {2} | G | + tn)}$

Использование Векторы Шрайера может иметь существенное влияние на производительность реализаций алгоритма Шрайера – Симса.

За Монте-Карло вариантов алгоритма Шрайера – Симса, мы имеем следующую оценку сложности:

{ Displaystyle О (п журнал п журнал ^ {4} | G | + tn журнал | G |)}

требуется память

{ Displaystyle О (п журнал | G | + tn)}

В современных системах компьютерной алгебры, таких как ЗАЗОР и Магма, оптимизированный Алгоритм Монте-Карло обычно используется.

Схема основного алгоритма

Ниже приводится псевдокод в стиле C ++ для основной идеи алгоритма Шрайера-Симса. Он предназначен для того, чтобы упустить все более тонкие детали, такие как управление памятью или любую низкоуровневую оптимизацию, чтобы не запутать наиболее важные идеи алгоритма. Собственно компилировать его не нужно.

структура Группа{  uint stabPoint;  // Индекс в базу для точки, стабилизированной подгруппой этой группы.  ОрбитаДерево орбитаДерево; // Дерево для отслеживания орбиты в нашей группе точки, стабилизированной нашей подгруппой.  TransversalSet transversalSet; // Набор представителей смежного класса подгруппы данной группы.  Генераторная установка генераторная установка; // Набор перестановок, порождающий эту группу.  Группа* подгруппа; // Указатель на подгруппу этой группы или ноль для обозначения тривиальной группы.  Группа(uint stabPoint)  {    это->stabPoint = stabPoint;    подгруппа = nullptr;  }};// Данный набор генераторов не обязательно должен быть сильным. Ему просто нужно сгенерировать группу в корне цепочки.Группа* MakeStabChain(const Генераторная установка& генераторная установка, uint* основание){  Группа* группа = новый Группа(0);  за (генератор в генераторная установка)    группа->Продлевать(генератор, основание);  возвращаться группа;}// Расширяем цепочку стабилизатора с корнем в этой группе с помощью данного генератора.пустота Группа::Продлевать(const Перестановка& генератор, uint* основание){  // Это основная оптимизация Schreier-Sims. Откажитесь от избыточных генераторов Шрайера.  если (IsMember(генератор))    возвращаться;  // Наша группа только увеличилась, но цепочка стабилизаторов, основанная на нашей подгруппе, осталась прежней.  генераторная установка.Добавлять(генератор);  // Исследуем все новые орбиты, которых мы можем достичь с добавлением нового генератора.  // Обратите внимание, что если дерево изначально было пустым, идентификатор должен быть возвращен  // в наборе, чтобы удовлетворить условию леммы Шрайера.  newTerritorySet = орбитаДерево.Расти(генератор, основание);  // По теореме о стабилизаторе орбиты перестановки в возвращаемом наборе  // представители смежных классов нашей подгруппы.  за (перестановка в newTerritorySet)    transversalSet.Добавлять(перестановка);  // Теперь применим лемму Шрайера, чтобы найти новые образующие для нашей подгруппы.  // Некоторые итерации этого цикла избыточны, но для простоты мы это игнорируем.  за (cosetRepresentative в transversalSet)  {    за (генератор в генераторная установка)    {      SchreierGenerator = CalcSchreierGenerator(cosetRepresentative, генератор);      если (SchreierGenerator.IsIdentity())        Продолжить;            если (!подгруппа)        подгруппа = новый Группа(stabPoint + 1);      подгруппа->Продлевать(SchreierGenerator, основание);    }  }}

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

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

Алгоритм Шрайера – Симса - Schreier–Sims algorithm

Предпосылки и сроки

Схема основного алгоритма

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