[GAP Forum] Re: complexity of the "orbit" function

[Alexander Hulpke]

>>

Dear Forum,

  Miguel Marco asked:

> I am doing some calculations that involve calculating the orbit of  
> permutation
> groups over sets of sets. The problem is that in some cases, the  
> procedure
> excedes the memory of my computer. I want to detect when will that  
> happen, in
> order to separate the cases where that calculation will take too  
> much memory
> from the rest.
> My question is: what does the complexity of the "orbit" function  
> deppend on?
> The order of the group?, the index of the stabilizer of the object?  
> And how
> can i estimate it before attempting to caluclate the actual orbit?
>

The ``sets of sets'' action does not use a backtrack, but an ordinary  
orbit algorithm. Time and memory complexity of this are proportional  
to the index of the stabilizer.

What you could do is fivefold:

- Change the permutation action (`ActionHomomorphism') to have the  
group act on sets, as Sven Reichard already described in his mail.  
You then could use the simple set-stabilizer, however the cost ois  
that the degree can go up substantially.

- Separate sets of different size (they cannot be mixed) and  
calculate the stabilizer iteratively. Similarly, if your group is not  
transitive you can separate acording to group orbits.

- Can you compute a subgroup, that must contain the stabilizer? (For  
example, if your sets of sets do not contain all points, you could  
calculate the (set-)stabilizer of the union first.

- If your degree is not too big, one can write down the set-of-set  
stabilizer in the symmetric group (it is a direct product of wreath  
products). One then could calculate the intersection with the  
original group.

- You could calculate the stabilizer of all the sets first, this will  
give you a subgroup of your stabilizer. The set-of-set stabilizer  
then is larger with index at most k! if you have k sets.

What strategy will be promising depends very much on the groups and  
sets in question -- feel free to send us (support at gap-system.org) a  
``typical'' example and we might be able to give a better idea on  
strategies.

Best wishes,

      Alexander Hulpke


-- Colorado State University, Department of Mathematics,
Weber Building, 1874 Campus Delivery, Fort Collins, CO 80523-1874, USA
email: hulpke at math.colostate.edu, Phone: ++1-970-4914288
http://www.math.colostate.edu/~hulpke