Schreier–Sims algorithm: Difference between revisions

Revision as of 23:34, 11 August 2004

Revision as of 23:36, 11 August 2004

Line 1:

The '''Schreier-Sims algorithm''' is an efficient method of computing a [[strong generating set]] (SGS) 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|computer algebra systems]]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|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>

* <math>O(n^32 \log^3 |G| + tn^2 \log |G|) </math> requiring memory <math>O(n^2 \log^2 |G| + tn) </math>

* <math>O(n^23 \log^3 |G| + tn^2 \log |G|) </math> requiring memory <math>O(n^2 \log^2 |G| + tn) </math>

For [[Monte Carlo]] variations of the Schreier-Sims algorithm, we have the following estimated complexity:

*: <math>O(n \log n \log^4 |G| + tn \log |G|)</math> requiring memory <math>O(n \log |G| + tn)</math>

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

[[Category:Algorithms]]