Schreier-Sims algorithm

The Schreier-Sims algorithm is an efficient method of computing a strong generating set (SGS) of a permutation group. In particular, an SGS determines the order of a group and makes it easy to test membership in the group. Since the SGS is critical for many algorithms in computational group theory, computer algebra systems typically rely on the Schreier-Sims algorithm for efficient calculations in groups.

The running time of Schreier-Sims varies on the implementation. Let G \leq S_n be given by t generators. For the deterministic version of the algorithm, possible running times are:

  • O(n2log3 | G | + tnlog | G | ) requiring memory O(n2log | G | + tn)
  • O(n3log3 | G | + tn2log | G | ) requiring memory O(nlog2 | G | + tn)

For Monte Carlo variations of the Schreier-Sims algorithm, we have the following estimated complexity:

O(nlognlog4 | G | + tnlog | G | ) requiring memory O(nlog | G | + tn)

In computer algebra systems, an optimized Monte Carlo algorithm is typically used.

See also Schreier's subgroup lemma.

References

  • Seress, A. Permutation Group Algorithms. Cambridge U Press, 2002.


This article is licensed under the GNU Free Documentation License. It uses material from Wikipedia article. Browse Wikipedia for more information.