Content deleted Content added
Luke Maurits (talk | contribs) m Clarified that the algorithm produces a SGS relative to a base which the algorithm can generate from a partial base. Linked to base article. |
m (partially) disambiguate a link to generator |
||
Line 1:
The '''Schreier-Sims 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:
* <math>O(n^2 \log^3 |G| + tn \log |G|) </math> requiring memory <math>O(n^2 \log |G| + tn)</math>
| |||