# Not really blogging

A. Makelov

## Google Summer of Code 2012: Week 2

June 2, 2012

Posted by on Hi everyone,

Here is a brief summary of what I’ve been doing for the second week of my GSoC.

The first main direction was randomization: an implementation of the **product replacement algorithm using an optimization suggested by Leedham-Green, as described in [1]**. After an initialization that takes ~ 50 group operations (a number suggested by [1] to be large enough for practical purposes), group elements the properties of which are satisfyingly random for most CGT algorithms can be produced at the cost of one group operation (in the context of permutation groups, by a ‘group operation’ we mean the multiplication of two permutations of size the degree of the permutation group). Thus the time complexity here is O(n).

The product replacement algorithm allowed the implementation of a simple (yet backed up by some nontrivial results in number theory and group theory) and fast Monte Carlo algorithm for **testing whether a given permutation group is the symmetric or the alternating group** (once we know this, it is straightforward to decide which one it is by checking the parity of all the generators). This is suggested in [1] as a first step in analyzing a large permutation group. It should be noted that the algorithm is actually one-sided Monte Carlo (as defined in [2]): a wrong answer is guaranteed to be wrong, whereas a right answer may be wrong with some predefined probability. The complexity here is O(n log(n)).

The second direction was **computing minimal blocks by Atkinson’s algorithm**. A function taking several points S from {0, 1, …, n-1} for a transitive permutation group G of degree n, and returning the maximal block system of G (meaning the one with the smallest block size) such that the points in S are contained in the same block, was implemented. The time complexity is just above O(|S|n) ([1]). Atkinson’s algorithm itself makes use of the union-find algorithm (of course, with path compression and union by rank) to manage an equivalence relation on the set {0, 1, …, n-1}.

As a consequence of this, **primitivity testing** in O(n^2) time is possible (we just check for blocks containing {0, 1}, {0, 2},…, {0, n-1}). There are three optimizations to this suggested in [1] that were implemented:

- Compute the stabilizer Stab of 0 and look at {0, rep} for orbit representatives of the action of Stab on {0, …, n-1}
- Stop the merging process once an equivalence class becomes larger than n/p where p is the smallest prime dividing n (as block sizes must divide n)
- Instead of computing the stabilizer deterministically, take a subgroup generated by several random elements from Stab, by a slight modification of product replacement for G.

Still, the algorithm runs for O(n^2) time and will perform badly if Stab is small. There are primitivity testing algorithms that run in almost linear time (one is suggested in [2]), but it is claimed in [1] that the use of Atkinson’s algorithm performs well for permutation groups with degrees in the millions (which is good for our purposes) — so the question of performance here needs some further investigation.

There were some other minor changes made:

- The group constructors for Sym and Alt now don’t calculate the order of the group right away, but only when the order is called for ( factorial(1000000) used to take almost all the time for initializing SymmetricGroup(1000000)).
- The function orbit() can now compute the union of the orbits for several points, or the orbit of an ordered tuple of elements of {0, 1,…, n-1}. It would be desirable to be able to do this for unordered tuples as well – but the effectiveness of this might become very low since sets are not hashable in python. Perhaps there is some way to get around this.

Several changes in design were proposed in the pull request for week1 that deserve consideration (and discussion).

[1] Derek F. Holt, Bettina Eick, Bettina, Eamonn A. O’Brien, “Handbook of computational group theory”, Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL, 2005. ISBN 1-58488-372-3

[2] Permutation Group Algorithms, Ákos Seress, Cambridge University Press

Advertisements

>sets are not hashable in python. Perhaps there is some way to get around this.

you might use frozenset

LikeLike

Indeed, this is going to work 🙂 Thanks a lot!

LikeLike

Here’s the branch with the code for week 2: https://github.com/amakelov/sympy/tree/week2

Since the code from week 1 is not merged yet, the pull request is probably going to have to wait for a while.

LikeLike

Pingback: Google Summer of Code 2012: Week 5 « Not really blogging