Schreier–Sims algorithm: Difference between revisions

Revision as of 16:52, 18 January 2009

Revision as of 05:09, 14 April 2009

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 [[DonDonald Knuth]] in 1991. Later, an even faster [[Randomized algorithm|randomized]] version of the algorithm was developed.

== Background and timing ==