> < ^ From:

> < ^ Subject:

Leonard Soicher writes in his e-mail message of 1994/07/26

Why does Gap feel it is necessary to compute a stabilizer chain for G in

order to compute RepresentativeOperation(G,1,pt) ?

I just looked at the code. Superficially it appears to be the result of

a mixture of stupidity and laziness. In truth however, I used the most

stupid and wastefull method I could think of, to see how long it would go

undetected ;-).

Leonard continues in his e-mail message of 1994/07/27

I suggest the following default strategy for calculating

RepresentativeOperation(G,x,y,action);The idea is to build up two partial Schreier trees Tx, Ty (w.r.t.

G.generators), rooted at x and y, respectively. One alternately

adds nodes to Tx and Ty until they have a node z, say, in common (if

one of the trees is completed and there is no such node then return

false). Given such a z, one uses Tx,Ty in the usual way to

get elements gx,gy such that z=action(x,gx)=action(y,gy),

and so the required element taking x to y is gx/gy.If x and y are in the same G-orbit, then this approach should be

much faster than computing an orbit for x until y is found, and

much much faster than trying to compute a StabChain if the action is

OnPoints.

It is not clear to me that this is indeed a win. Let us assume that the

group operates transitively on $n$ points and that it has only a small

number $k$ of generators.

Then computing the entire orbit an the corresponding Schreier tree takes

time $O( n k )$. Your method on the other hand would usually take time

$O( n^(1/2) k )$ (the worst case is of course also $O( n k )$.

However, I think that in most cases the total time will anyhow be

dominated by the time it takes to multiply together the representative.

Namely, under favourable conditions the pathlength from $x$ to $y$ in

this tree will be $O( log(n) )$, so the cost of computing the

representative is $O( n log(n) )$.

So your method would not be faster unless $k >> log(n)$. This is only

theory of course, and I haven't yet investigated this in practice. It

might well be that the constant for the orbit computation is so much

higher that the constant for the representative computation (most of

which is multiplying permutations, and this is done in the kernel), that

your method is still practically better.

However, there is even a practical argument against your method. Namely

assume that a user makes multiple calls to 'RepresentativeOperation',

maybe with fixed 'x' but varying 'y'. With the straightforward orbit

computation one could compute the orbit once and then remember it, so

that subsequent calls to 'RepresentativeOperation' do not have to

recompute it. With your method it is not clear how to do this, so that

the total time for all tree computations never exceeds $O( n k )$.

Martin.

-- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany

> < [top]