Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Schreier–Sims algorithm
Summary
The Schreier–Sims algorithm is an algorithm in computational group theory, named after the mathematicians Otto Schreier and Charles Sims. This algorithm can find the order of a finite permutation group, test membership (is a given permutation contained in a group?), and many other tasks in polynomial time. It was introduced by Sims in 1970, based on Schreier's subgroup lemma. The timing was subsequently improved by Donald Knuth in 1991. Later, an even faster randomized version of the algorithm was developed.
The algorithm is an efficient method of computing a 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 systems typically rely on the Schreier–Sims algorithm for efficient calculations in groups.
The running time of Schreier–Sims varies on the implementation. Let be given by generators. For the deterministic version of the algorithm, possible running times are:
requiring memory
requiring memory
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:
requiring memory
In modern computer algebra systems, such as GAP and Magma, an optimized Monte Carlo algorithm is typically used.
Following is C++-style pseudo-code for the basic idea of the Schreier-Sims algorithm. It is meant to leave out all finer details, such as memory management or any kind of low-level optimization, so as not to obfuscate the most important ideas of the algorithm. It does not need to actually compile.
struct Group
{
uint stabPoint; // An index into the base for the point stabilized by this group's subgroup.
OrbitTree orbitTree; // A tree to keep track of the orbit in our group of the point stabilized by our subgroup.
TransversalSet transversalSet; // A set of coset representatives of this group's subgroup.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.