Revision as of 11:15, 1 February 2006 edit Charles Matthews (talk \| contribs) Autopatrolled, Administrators 367,753 edits m +cat ← Previous edit		Revision as of 14:48, 2 February 2006 edit undo Luke Maurits (talk \| contribs) 105 edits 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. Next edit →
Line 1: The '''Schreier-Sims algorithm''' is an efficient method of computing a [[base_(group_theory)\|base]] and [[strong generating set]] (~~SGS~~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\|generators]]. For the [[deterministic]] version of the algorithm, possible running times are: Line 5: * <math>O(n^2 \log^3 \|G\| + tn \log \|G\|) </math> requiring memory <math>O(n^2 \log \|G\| + tn)</math> * <math>O(n^3 \log^3 \|G\| + tn^2 \log \|G\|) </math> requiring memory <math>O(n \log^2 \|G\| + tn) </math> The use of [[Schreier vector\|Schreier vectors]] can have a significant influence on the performance of implementations of the Schreier-Sims algorithm. For [[Monte Carlo algorithm\|Monte Carlo]] variations of the Schreier-Sims algorithm, we have the following estimated complexity:

Schreier–Sims algorithm: Difference between revisions