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

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

Предыстория и время

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

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

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

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

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

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

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

Краткое описание основного алгоритма

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

struct Group
{
  uint stabPoint;  // An index into the base for the point stabilized by this group's subgroup.
  OrbitTree orbitTree; // A tree to keep track of the orbit in our group of the point stabilized by our subgroup.
  TransversalSet transversalSet; // A set of coset representatives of this group's subgroup.
  GeneratorSet generatorSet; // A set of permutations generating this group.
  Group* subGroup; // A pointer to this group's subgroup, or null to mean the trivial group.

  Group(uint stabPoint)
  {
    this->stabPoint = stabPoint;
    subGroup = nullptr;
  }
};

// The given set of generators need not be a strong generating set.  It just needs to generate the group at the root of the chain.
Group* MakeStabChain(const GeneratorSet& generatorSet, uint* base)
{
  Group* group = new Group(0);
  for (generator in generatorSet)
    group->Extend(generator, base);
  return group;
}

// Extend the stabilizer chain rooted at this group with the given generator.
void Group::Extend(const Permutation& generator, uint* base)
{
  // This is the major optimization of Schreier-Sims.  Weed out redundant Schreier generators.
  if (IsMember(generator))
    return;

  // Our group just got bigger, but the stabilizer chain rooted at our subgroup is still the same.
  generatorSet.Add(generator);

  // Explore all new orbits we can reach with the addition of the new generator.
  // Note that if the tree was empty to begin with, the identity must be returned
  // in the set to satisfy a condition of Schreier's lemma.
  newTerritorySet = orbitTree.Grow(generator, base);

  // By the orbit-stabilizer theorem, the permutations in the returned set are
  // coset representatives of the cosets of our subgroup.
  for (permutation in newTerritorySet)
    transversalSet.Add(permutation);

  // We now apply Schreier's lemma to find new generators for our subgroup.
  // Some iterations of this loop are redundant, but we ignore that for simplicity.
  for (cosetRepresentative in transversalSet)
  {
    for (generator in generatorSet)
    {
      schreierGenerator = CalcSchreierGenerator(cosetRepresentative, generator);
      if (schreierGenerator.IsIdentity())
        continue;
      
      if (!subGroup)
        subGroup = new Group(stabPoint + 1);

      subGroup->Extend(schreierGenerator, base);
    }
  }
}

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

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

Ссылки

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