# Not really blogging

A. Makelov

## Google Summer of Code 2012: Week 4

Hi everyone,

Here’s a brief summary of what I’ve been doing for the 4-th week of my GSoC.

This week, like the previous one, was not intense in terms of coding. Here’s what I have up and running, basically what I was talking about last week:

• A working implementation of the randomized Schreier-Sims algorithm. This still needs to be integrated with the deterministic version of the algorithm, using the fields  _base, _coset_repr, _coset_repr_n, stabilizers_gens so that a result from the randomized algorithm can be verified deterministically. Also, it’s been suggested that we have a function that determines the base and transversal elements for the basic orbits by a given generating set that is known to be strong. This won’t be hard to implement, and will be helpful for the Butler-Portugal algorithm for tensor canonicalization – see this pull request for more information if you are interested! For more on bases and strong generating sets, see [1], pp.101-119
• A function $\text{DirectProduct(*groups)}$ that constructs the direct product of several groups. For more than two groups, $\text{DirectProduct}(G_1,\ldots, G_n)$ is several times faster than calling $G_1*\ldots * G_n$ (benchmarked it), thus it makes sense to have such a function. This is later used in constructing an arbitrary abelian group by its cycle decomposition.
• A function for calculating the degree of transitivity of a permutation group. The idea is very brute-force: we look at the orbit of a $k+1$-tuple $(0, 1, \ldots, k)$ for $k = 0, 1, \ldots, n-1$ and check if it spans all possible $k+1$-tuples. This is really bad since the number of tuples is growing like $n^{k+1}$, hence the complexity is $O(n^{k+1}r)$ where $k$ is the degree of transitivity, $r$ is the number of generators. It seems that some sort of randomization that checks only several randomly chosen tuples for membership in the orbit will decrease the complexity, but to make sure we still need to do all the checks if the random tuples pass, which is again $O(n^{k+1}r)$. Some bound on the probability will be good to know here.

The main focus this week was on several discussions about future changes in the permutation groups module, and on making some more effort to get my code so far merged 🙂 :

• In this post to the mailing list, it was suggested to implement an algorithm for intersecting subgroups of a given group so that it can be used in the tensor canonicalization algorithm (again, see here). This is done in [1] but seems fairly complicated and opens the subject of backtrack searches in permutation groups; I’ll try to figure it out and implement it this coming week.
• In this post to the mailing list, we discussed ways of testing randomized algorithms (and there are a lot of them involved in computational group theory), and an agreement was reached that some sort of manual setting of the randomized output (via an additional argument) is a sensible approach.
• In this post to the mailing list, we discussed some changes in interface in the permutations module. Even though not everybody agrees with what I last suggested, I’ll carry these changes out and see how things unfold (i.e., whether people are happy)
• Finally, my work from week 1 is, I hope, ready to be merged, now that I’ve made the changes suggested in the discussion of the pull request . I (finally) got familiar with the sphinx system and building the docs for sympy, and with all the conventions for writing docstrings (and convinced myself that I’ve been writing them the wrong way, I’ll fix all the docstrings in the module in the future). By the way, I installed the sphinx system in a virtualenv at the suggestion of S. Krastanov, and found the following guide really helpful in the process. When the week1 branch gets merged, a pull request with the week2 code will follow shortly, and then with the rest of the code so far…
• And in this discussion, there were some more changes suggested, for example David proposed isolating the named groups (Symmetric, Dihedral, …) in a separate module, which I’m going to do in one of the next pull requests.

So, that’s it for now. Next week I’ll focus on getting some more of my code merged and backtrack searches.

[1] Holt, D., Eick, B., O’Brien, E. “Handbook of computational group theory”

### 3 responses to “Google Summer of Code 2012: Week 4”

1. Jason B Hill June 18, 2012 at 3:10 am

As for using the deterministic version of Schreier-Sims to verify correctness of the random version, I would suggest instead to use Sims’ “verify routine” (as GAP does by default to force correctness). See, for instance, section 8.2 in Seress’ text.

Like

2. amakelov June 19, 2012 at 10:50 am

Yes, that indeed makes more sense. I also found a description of the verify routine in the Handbook (which seems to be more accessible at the moment). However, presentation stuff is involved, so I’ll have to go over it more carefully and see if it needs something related to the Todd-Coxeter algorithm (which I’ll be implementing anyway). My current concern is for the group intersection algorithm which needs Schreier-Sims, but the current deterministic implementation will work for the time being.

Like

mathbabe

Exploring and venting about quantitative issues

Rational Altruist