Google Summer of Code 2012: Week 3
June 10, 2012Posted by on
there wasn’t much coding done on my project this week; I’ve been going over the different versions of the Schreier-Sims algorithm as described in ; there is currently an implementation with using Jerrum’s filter as an optimization (see this), and I’ve almost implemented the faster randomized version described in . It remains to see how to integrate both so that the output of the randomized version can be verified, and how to use the deterministic implementation in order to do variations of the Schreier-Sims algorithm, for example when the order of the group is known in advance, or when a base is known. Also, it might be appropriate to switch between storing transversals explicitly (requires a lot of memory, but increases speed) and using schreier vectors insted (much less memory, slower access to transversal elements) depending on the degree of the permutation group.
Apart from that, there’s been work on:
- Finding the degree of transitivity for a permutation group: using the function orbit as acting on tuples of points, but the algorithm is sort of brute-force and becomes large for groups of large degree or large degree of transitivity.
- Constructing abelian groups as permutation groups, by their decomposition as a direct sum of cyclic groups of given orders (per the classification of finite abelian groups), i.e. is the group isomorphic to
My code from the first two weeks is not yet merged, so next week I’ll focus on getting my pull requests reviewed, and will probably do a combined pull request next week including the code from this week. The discussion I started on the mailing list received some attention and it is now a bit clearer what changes to the interface are going to be desirable. Also, it seems that a wider array of available groups to work with will be helpful for testing purposes (i.e., groups of large degree with a small base and other interesting types of groups).
 Holt, D., Eick, B., O’Brien, E. “Handbook of computational group theory”