All you need is graphs (to compute orbital closures in GAP).

by Markus Pfeiffer

Finishing some long overdue work, I was recently benchmarking different ways to compute orbital closures of permutation groups.

Or­bital Clo­sures, and what oth­ers call them

Let’s first lay down what I am computing. I have referred to Orbital Graphs before.

Suppose that \Omega = \{1..n\} for some n \in \mathbb{N} and G \leq S_{\Omega}.

We consider all all orbital graphs of G by considering all possible base pairs and intersect their automorphism groups. The result of this operation is called the orbital closureor the 2-closure of G, or the automorphism group of an association scheme.

\mathcal{OC}(G) = \bigcap\limits_{(\alpha,\beta) \in \Omega^2} \operatorname{Aut}(\Gamma_{(\alpha,\beta)})

of GWhich necessarily contains G, but might be bigger.

Naive com­pu­ta­tions

In GAP using the package digraphs, and optionally ferret, one can naively compute the group \mathcal{OC}\left(G\right) as follows

1
2
3
4
5
6
Or­bital­Clo­sure := func­tion(G)
  lo­cal ogs, ogauts;
  ogs := Or­bital­Graphs(G);
  ogauts := List(ogs, Au­to­mor­phism­Group);
  re­turn In­ter­sec­tion(ogauts);
end;

The code above becomes unbearably slow if we maliciously produce examples of groups with a decent number of orbital graphs, such as direct products of isomorphic groups or even a wreath product.

Trying to compute the orbital closure of G = D_{32} \wr D_{32} makes the wait already quite painful.

Exploring what takes so long in this computation yields some insight: We compute the automorphism group of each orbital graph separately, intersecting the results. Group intersection is a hard problem, though it is no harder than graph automorphism finding.

Clev­er­er con­struc­tion

A slightly cleverer way of computing the orbital closure is not to compute a truckload of graphs, their automorphism groups, and intersecting them, but to just compute one graph with coloured edges, where the edges represent which orbital graph it belongs to, and handing that to a graph automorphism solver. This should of course yield the same result, but using a very efficient graph automorphism finder works a lot better.thanks go to Finn Smith for adding code to the GAP package digraphs to compute automorphisms of edge-coloured digraphs

Bench­marks in GAP with Di­graphs and fer­ret

Putting this together I did some benchmark comparisons using GAP 4.11, digraphs, and ferret and found that the edge-coloured method is up to a factor of 1000 faster. Hence the new default method in the orbitalgraphs package is using the edge-coloured graph method as a default when one calls OrbitalClosure(G).

The following table shows the computation time (in milliseconds) for the orbital closure of D_{32} \wr D_{2n} for n \in \{4 \ldots 11\}. The second column contains the number of distinct orbital graphs.

n #or­bital graphs in­ter­sect edge-coloured
4 10 588.818 7.810
5 10 876.719 9.932
6 11 2311.209 15.972
7 11 103966.205 21.423
8 12 301819.541 34.307
9 12 445608.635 34.193
10 13 824163.351 42.039
11 13 1657053.153 65.100

As a disclaimer it should be said that this comparison is to a degree probably unfair, as GAP spends a very long time in its stabilizer chain code, an issue we’re keen to address.

Even more so­phis­ti­ca­tion?

In a future post I will be looking at Johannes Hahn’s suggested pull request for the orbitalgraphs package to improve performance more by avoiding more graphs.