Алгоритм Шрайера–Симса

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

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

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

Время выполнения алгоритма Шрайера–Симса зависит от реализации. Пусть задано генераторами . Для детерминированной версии алгоритма возможные времена выполнения следующие:${\displaystyle G\leq S_{n}}$${\displaystyle т}$

• ${\displaystyle O(n^{2}\log ^{3}|G|+tn\log |G|)}$требующий памяти${\displaystyle O(n^{2}\log |G|+tn)}$
• ${\displaystyle O(n^{3}\log ^{3}|G|+tn^{2}\log |G|)}$требующий памяти${\displaystyle O(n\log ^{2}|G|+tn)}$

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

Вариации Монте -Карло алгоритма Шрайера–Симса имеют расчетную сложность:

${\displaystyle O(n\log n\log ^{4}|G|+tn\log |G|)}$требующий памяти .${\displaystyle O(n\log |G|+tn)}$

Современные системы компьютерной алгебры, такие как GAP и Magma , обычно используют оптимизированный алгоритм Монте-Карло .

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

struct Group { uint stabPoint ; // Индекс в базе для точки, стабилизированной подгруппой этой группы. OrbitTree orbitTree ; // Дерево для отслеживания орбиты в нашей группе точки, стабилизированной нашей подгруппой. TransversalSet transversalSet ; // Набор представителей смежного класса подгруппы этой группы. GeneratorSet generatorSet ; // Набор перестановок, генерирующих эту группу. Group * subGroup ; // Указатель на подгруппу этой группы или null для обозначения тривиальной группы.                 Группа ( uint stabPoint ) { this -> stabPoint = stabPoint ; subGroup = nullptr ; } } ;         // Данный набор генераторов не обязательно должен быть сильным генераторным набором. Он просто должен генерировать группу в корне цепочки. Group * MakeStabChain ( const GeneratorSet & generatorSet , uint * base ) { Group * group = new Group ( 0 ); for ( generator in generatorSet ) group -> Extend ( generator , base ); return group ; }                  // Расширить цепочку стабилизаторов, основанную на этой группе, с помощью заданного генератора. void Group::Extend ( const Permutation & generator , uint * base ) { // Это основная оптимизация Schreier-Sims. Удалить лишние генераторы Schreier. if ( IsMember ( generator )) return ;          // Наша группа только что стала больше, но стабилизирующая цепь, основанная на нашей подгруппе, осталась прежней. generatorSet . Add ( generator );  // Исследуем все новые орбиты, которых мы можем достичь с добавлением нового генератора. // Обратите внимание, что если дерево изначально было пустым, то идентификатор должен быть возвращен // в наборе, чтобы удовлетворить условию леммы Шрайера. newTerritorySet = orbitTree . Grow ( generator , base );       // По теореме о стабилизаторе орбиты перестановки в возвращаемом наборе являются // представителями смежных классов нашей подгруппы. for ( permutation in newTerritorySet ) transversalSet . Add ( permutation );       // Теперь применим лемму Шрайера, чтобы найти новые генераторы для нашей подгруппы. // Некоторые итерации этого цикла избыточны, но мы игнорируем это для простоты. for ( cosetRepresentative in transversalSet ) { for ( generator in generatorSet ) { schreierGenerator = CalcSchreierGenerator ( cosetRepresentative , generator ); if ( schreierGenerator.IsIdentity ( ) ) continue ; if ( ! subGroup ) subGroup = new Group ( stabPoint + 1 ) ;                            подгруппа -> Расширить ( schreierGenerator , base ); } } }   

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

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

• Кнут, Дональд Э. «Эффективное представление пермских групп». Combinatorica 11 (1991), № 1, 33–43.
• Сересс, А., Алгоритмы групп перестановок , Cambridge U Press, 2002.
• Симс, Чарльз К. «Вычислительные методы в изучении групп перестановок», в сборнике « Вычислительные проблемы абстрактной алгебры» , стр. 169–183, Pergamon, Оксфорд, 1970.