- Schreier-Sims algorithm
The Schreier-Sims algorithm is an efficient method of computing a base and
strong generating set (BSGS) of apermutation 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 incomputational 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 G leq S_n be given by t generators. For the
deterministic version of the algorithm, possible running times are:* O(n^2 log^3 |G| + tn log |G|) requiring memory O(n^2 log |G| + tn)
* O(n^3 log^3 |G| + tn^2 log |G|) requiring memory O(n log^2 |G| + tn)The use of Schreier vectors can have a significant influence on the performance of implementations of the Schreier-Sims algorithm.
For Monte Carlo variations of the Schreier-Sims algorithm, we have the following estimated complexity:
: O(n log n log^4 |G| + tn log |G|) requiring memory O(n log |G| + tn)
In computer algebra systems, an optimized
Monte Carlo algorithm is typically used.See also
Schreier's subgroup lemma .References
*Seress, A. Permutation Group Algorithms. Cambridge U Press, 2002.
Wikimedia Foundation. 2010.