Not really blogging

A. Makelov

Google Summer of Code 2012: Week 2

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

4 responses to “Google Summer of Code 2012: Week 2

  1. mario June 3, 2012 at 3:11 pm

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

    you might use frozenset

    Like

  2. amakelov June 3, 2012 at 10:08 pm

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

    Like

  3. amakelov June 5, 2012 at 2:06 pm

    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.

    Like

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

mathbabe

Exploring and venting about quantitative issues

Rational Altruist

Adventures of a would-be do-gooder.

Gowers's Weblog

Mathematics related discussions

What's new

Updates on my research and expository papers, discussion of open problems, and other maths-related topics. By Terence Tao

Stefan's Blog (archive, for news see blog.krastanov.org)

Most of the blog moved to blog.krastanov.org

%d bloggers like this: