Schreier–Sims algorithm: Difference between revisions

Revision as of 16:37, 9 May 2017

Latest revision as of 19:53, 19 June 2024

(12 intermediate revisions by 9 users not shown)

Line 1:

{{Short description|Algorithm for solving various problems in computational group theory}}

The '''Schreier–Sims algorithm''' is an [[algorithm]] in [[computational group theory]] named after mathematicians [[Otto Schreier]] and [[Charles Sims (mathematician)|Charles Sims]]. Once performed, it allows a linear time computation of the [[Order (group theory)|order]] of a finite permutation group, group membership test (is a given permutation contained in a group?), and many other tasks. The algorithm was introduced by Sims in 1970, based on [[Schreier's subgroup lemma]]. The timing was subsequently improved by [[Donald Knuth]] in 1991. Later, an even faster [[Randomized algorithm|randomized]] version of the algorithm was developed.

{{inline|date=June 2024}}

The '''Schreier–Sims algorithm''' is an [[algorithm]] in [[computational group theory]], named after the mathematicians [[Otto Schreier]] and [[Charles Sims (mathematician)|Charles Sims]]. OnceThis performed,algorithm itcan allows a linear time computation offind the [[Order (group theory)|order]] of a finite permutation group, group membershipdetermine test (iswhether a given permutation contained inis a member of the group?), and many other tasks. in The[[polynomial algorithmtime]]. It was introduced by Sims in 1970, based on [[Schreier's subgroup lemma]]. The timing[[running time]] was subsequently improved by [[Donald Knuth]] in 1991. Later, an even faster [[Randomized algorithm|randomized]] version of the algorithm was developed.

== Background and timing ==

Line 12 ⟶ 14:

The use of [[Schreier vector]]s can have a significant influence on the performance of implementations of the Schreier–Sims algorithm.

ForThe [[Monte Carlo algorithm|Monte Carlo]] variations of the Schreier–Sims algorithm, we have the following estimated complexity:

: <math>O(n \log n \log^4 |G| + tn \log |G|)</math> requiring memory <math>O(n \log |G| + tn)</math>.

In modernModern computer algebra systems, such as [[GAP computer algebra system|GAP]] and [[Magma computer algebra system|Magma]], typically use an optimized [[Monte Carlo algorithm]] is typically used.

== Outline of basic algorithm ==

Following is C++-style pseudo-code for the basic idea of the Schreier-Sims algorithm. It is meant to leave out all finer details, such as memory management or any kind of low-level optimization, so as not to obfuscate the most important ideas of the algorithm. ItIts doesgoal is not need to actually compile.

<sourcesyntaxhighlight lang="cpp">

struct Group

{

Line 31 ⟶ 33:

Group* subGroup; // A pointer to this group's subgroup, or null to mean the trivial group.

Group( uint stabPoint )

{

this->stabPoint = stabPoint;

Line 39 ⟶ 41:

// 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 );

}

}

}

</syntaxhighlight>

Notable details left out here include the growing of the orbit tree and the calculation of each new Schreier generator. In place of the orbit tree, a [[Schreier vector]] can be used, but the idea is essentially the same. The tree is rooted at the identity element, which fixes the point stabilized by the subgroup. Each node of the tree can represent a permutation that, when combined with all permutations in the path from the root to it, takes that point to some new point not visited by any other node of the tree. By the [[orbit-stabilizer theorem]], these form a [[Transversal_(combinatorics)#Examples|transversal]]{{dn|date=May 2017}} of the subgroup of our group that stabilizes the point whose entire orbit is maintained by the tree. Calculating a Schreier generator is a simple matterapplication of applyingthe [[Schreier's subgroup lemma]].

</source>

Notable details left out here include the growing of the orbit tree and the calculation of each new Schreier generator. In place of the orbit tree, a [[Schreier vector]] can be used, but the idea is essentially the same. The tree is rooted at the identity element, which fixes the point stabilized by the subgroup. Each node of the tree can represent a permutation that, when combined with all permutations in the path from the root to it, takes that point to some new point not visited by any other node of the tree. By the [[orbit-stabilizer theorem]], these form a [[transversal]]{{dn|date=May 2017}} of the subgroup of our group that stabilizes the point whose entire orbit is maintained by the tree. Calculating a Schreier generator is a simple matter of applying [[Schreier's subgroup lemma]].

Another detail left out is the membership test. This test is based upon the sifting process. A permutation is sifted down the chain at each step by finding the containing coset, then using that coset's representative to find a permutation in the subgroup, and the process is repeated in the subgroup with that found permutation. If the end of the chain is reached (i.e., we reach the trivial subgroup), then the sifted permutation was a member of the group at the top of the chain.

==References==

* [[Knuth, Donald E.]] "Efficient representation of perm groups". '' Combinatorica'' 11 (1991), no. 1, 33–43.

* Seress, A., ''Permutation Group Algorithms'', Cambridge U Press, 2002.

* [[Charles Sims (mathematician)|Sims, Charles C.]] "Computational methods in the study of permutation groups", in ''Computational Problems in Abstract Algebra'', pp.&nbsp;169–183, Pergamon, Oxford, 1970.

{{DEFAULTSORT:Schreier-Sims algorithm}}