Schreier–Sims algorithm: Difference between revisions

Revision as of 03:26, 19 October 2010

Revision as of 09:47, 19 January 2011

Line 1:

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