Алгоритм Шрайера – Симса - 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)}$

В современных системах компьютерной алгебры, таких как 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);
    }
  }
}

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

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

Ссылки

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