> < ^ From:

^ Subject:

--6c2NcOVqGQ03X4Wi

Content-Type: text/plain; charset=iso-8859-1

Content-Disposition: inline

Content-Transfer-Encoding: quoted-printable

Dear GAP-Forum,

I sent a message a two months ago about a library I am developing for

computing in invariant rings of permutation groups. In the long term,

I am now pretty much convinced I need to rewrite it using GAP. I would

need advises concerning the first steps. My needs and current state of

development is detailed below.

Thanks in advance for any suggestions and comments,

Nicolas

---------------------------------------------------------------------------=

---

The main basic block I need for this is a set of blindingly fast

routines for isomorphisms problems of lists of integers under

permutation groups. I wrote a standalone C++ library (GLIP,

http://glip.sourceforge.net) to do this. I would like to either

integrate it into GAP, or happily throw it away if GAP already

provides the facilities I need.

Let me be more precise. Let G be a subgroup of the symmetric group Sn

over n elements. G acts naturally on lists of length n by permutation

of the elements (basic action Permuted). I consider here compositions,

i.e., lists of small non-negative integers. To give an order of

magnitude, here is a typical example I would be interested in:

G6:=3DAction(SymmetricGroup(6), Combinations([1..6],2), OnSets)

So, Size(G)=3D720, n=3D15, and by small integers, I mean in the range [0..3= 0].

Here are the different operations I need:

1 Orbit(l), compute the orbit of l

2 Canonic(l) compute the canonical representant of the orbit of l.

(by canonical, I mean for example maximum for lexicographic comparison)

3 IsCanonic(l) test if l is canonical in its orbit

4 CanonicCompositions(d) compute the canonical representants of all

orbits of compositions of sum d

5 CanonicCompositions(l) compute the canonical representants of all

orbits of compositions having the same content as l.

With the example above, 5 amounts to generating multigraphs up to

an isomorphism, and 6, with l=3D[1,1,1,0,...,0], amounts to generating simp=

le

graphs with 3 edges up to an isomorphism. There already exists software

doing this kind of thing (e.g. Nauty by Brendan Mc Kay), but I would

like my library to work more generally with any permutation group.

I would describe my current implementation as not-completely-stupid

brute force. I.e. the full group is directly generated, and a

canonical test which succeeds requires to iterate through the whole

group. On the other hand, the ordering of the elements of the group is

dynamically adapted, so as to statistically quickly reject

compositions that are not canonical. Also, 4 and 5 use orderly

generation techniques, which require almost constant memory space, and

should be reasonably fast, with an average complexity around (size of

the group) x (number of representants).

Using a backtrack algorithm based on stabilizer chains would probably

make canonical tests much faster in the average. It would also avoid

the generation of the group, though it may be worth to remember the

full backtrack tree in between calls to IsCanonic.

---------------------------------------------------------------------------= --- Here are some technical questions for which I did not manage to find answers in the manual.

1) To compute the Hilbert series of the invariant ring, and to do

Polya enumeration, I need to know how many permutations of G there

are of each given cycle type. To avoid generating the group, one

way can be to try to find the sizes of the conjugacy class of G,

and the cycle type of their respective elements. Is it possible to

get this information without actually computing

ConjugacyClasses(G)? For example, if G is obtained as the image of

a smaller group G' by some homomorphism, it would be nice to get

the information from G' and the homomorphism instead.

2) I often need to run through the (big) results of Partitions(...),

Combinations(...) or such. Are there non-trivial Iterators for

those structures ?

Related to this, is it possible to define the following action,

without actually generating of all the combinations?

G20:=3DAction(SymmetricGroup(20), Combinations([1..20],2), OnSets)

3) I will have to store a lot of compositions. Since the numbers

involved are small, it seems to be reasonable to store those

compositions as row vectors with coefficient in some small field

(e.g. GF(2^5)). Is the natural action Permuted defined (and

efficient) for such row vectors?

4) Is it possible to construct an infinite dimensional algebra by

providing an infinite set of linearly independent generators and

specifying the multiplication table through a function:

F(gen,gen) -> linear combination of generators ?

5) Is the "division by increasing powers" of univariate polynomials

implemented ?

6) I know a few persons would who have about the same needs as me for

the isomorphisms problem I stated above. However, they specifically

need a library that can be linked into another software. If the

final implementation is in GAP, is it technically possible to make

a (static or dynamic) module containing just the strictly necessary

parts of GAP ?

--=20 Nicolas M. Thi=E9ry "Isil", 412 Washington Avenue, 80403 Golden Colorado (U= SA) M=E9l: nthiery@mines.edu, T=E9l: (303)273-5492, Fax: (303)273-3875 WWW: <URL:http://www.mines.edu/~nthiery/>

--6c2NcOVqGQ03X4Wi

Content-Type: application/pgp-signature

Content-Disposition: inline

-----BEGIN PGP SIGNATURE-----

Version: GnuPG v1.0.0 (GNU/Linux)

Comment: For info see http://www.gnupg.org

iD8DBQE5wwVm6iQOIqkrTMQRAjzqAJ0U9R9dN1WJCLHizXKA28fGrRCFOQCfRV5M

bh+/aTNwHt43IqTPWLEUc3c=

=oHph

-----END PGP SIGNATURE-----

--6c2NcOVqGQ03X4Wi--

> < [top]