Schreier–Sims algorithm: Difference between revisions

Revision as of 04:05, 1 November 2008

Revision as of 17:30, 1 November 2008

Line 1:

The '''Schreier-Sims algorithm''' is an [[algorithm]] in [[computational group theory]] named after [[Otto Schreier]] and [[Charles Sims (mathematician)|Charles Sims]]. ItOne 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.

== 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-Sims algorithm for efficient calculations in groups.

The running time of Schreier-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: