Schreier–Sims algorithm: Difference between revisions

Revision as of 17:30, 1 November 2008

Revision as of 17:42, 1 November 2008

Line 1:

The '''Schreier-Sims algorithm''' is an [[algorithm]] in [[computational group theory]] named after mathematicians [[Otto Schreier]] and [[Charles Sims (mathematician)|Charles Sims]]. One 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 [[Don Knuth]] in 1991. Later, an even faster [[Randomized algorithm|randomized]] version of the algorithm was developed.

== Background and timing ==

Line 18:

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

See also [[Schreier's subgroup lemma]].

==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.

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

[[Category:Computational group theory]]