[GAP Forum] Fast Orbit Computation for Custom Objects?

Sven Reichard Sven.Reichard at tu-dresden.de
Fri May 17 09:53:55 BST 2013


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Dear Forum,

I have the following data:
- - A permutation group G;
- - a set of objects obj;
- - an action function.

I would like to get the following:
- - The union D of the orbits of obj under G (not necessarily sorted);
- - the action H of G on D;
- - orbit representatives.

What I do is the following:

orbits := Orbits(G, obj, action);
representatives := List(orbits, Representative);
D := Union(orbits); # sorted to accelerate the next step
H := Action(G, D, action);

This works well when action is a standard action such as OnSetsSets.
However, for custom actions this can be very slow, suggesting that
different algorithms are used. (In some of my examples, D has a
million elements.)

Is there a way in GAP4 to accelerate this process, for example by
providing hash functions? In GAP3 there existed a solution in the
contributed file coco.grp by Theißen based on work by Faradzev et al.
The question is whether there is a better way than porting that file
to GAP4.

Regards,
Sven Reichard.

- -- 

Institut für Algebra
TU Dresden
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.5 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/

iQEVAwUBUZXwI2FjB3Gki4XVAQJrDgf+IdzNftD5zutKuXm/7vOWQhSOe6ZdeJ8p
N+FWYHgXYuHfHPrXquv/iUzVKRaADu01+enk/T9sYIr6oEorcAO5GS0uh/5yhBSq
IqL5jsvkyCbrW3jN8sjGUZanGw5z81cjx5VoigYuaON8VMB8qGMQ6w20B+0XdTss
29YZJZz1r2JMNB/Lfx7iiqHCRalfK1+qnnvimro404H2jc+sjvGH83nh6z3uZLy4
eaDBOaJgI2Uz8Nz3SL2KBEzhQ02Ipem3jEC37izS9Or20zotcog/G3v0uLsy10/G
y7mcQ0lfhxH4PwQ1OpTbvFD4WHNQ1riMTmG5qtZgP9d7uymKBssmMA==
=JAOJ
-----END PGP SIGNATURE-----



More information about the Forum mailing list