Schreier–Sims algorithm: Difference between revisions

Revision as of 08:22, 8 February 2010

Revision as of 19:02, 9 February 2010

Line 1:

The '''Schreier-SimsSchreier–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 group, group membership test (is a given permutation contained in a group?), and many other tasks. The algorithm was introduced by Sims in 1970 and is based on the [[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.

== Background and timing ==

The algorithm is an efficient method of computing a [[base_(group_theory)|base]] and [[strong generating set]] (BSGS) 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 system]]s typically rely on the Schreier-SimsSchreier–Sims algorithm for efficient calculations in groups.

The running time of Schreier-SimsSchreier–Sims varies on the implementation. Let <math> G \leq S_n </math> be given by <math>t</math> [[generator (mathematics)|generators]]. For the [[deterministic]] version of the algorithm, possible running times are:

* <math>O(n^2 \log^3 |G| + tn \log |G|) </math> requiring memory <math>O(n^2 \log |G| + tn)</math>

* <math>O(n^3 \log^3 |G| + tn^2 \log |G|) </math> requiring memory <math>O(n \log^2 |G| + tn) </math>

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

For [[Monte Carlo algorithm|Monte Carlo]] variations of the Schreier-SimsSchreier–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>

Line 19:

==References==

* Knuth, Donald E. Efficient representation of perm groups. Combinatorica 11 (1991), no. 1, 33-4333–43.

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

* Sims, Charles C. Computational methods in the study of permutation groups, in Computational Problems in Abstract Algebra, pp. 169-183169–183, Pergamon, Oxford, 1970.

[[Category:Computational group theory]]