> < ^ From:

< ^ Subject:

I wrote in my e-mail message of 1994/07/28

...about computing a representative that takes x to y...

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) )$.

Steve Linton answered in his e-mail message of 1994/07/28

This is only so if the action is on points. Suppose that we consider

a permutation group of small degree acting on a large orbit of sets

or tuples, or a matrix group of small degree acting on vectors or

subspaces. Then the time for a multiplication is much less than n.

For the operation on tuples you use a stabilizer chain. That is you

first find a representative r_1 that moves x[1] to y[1]. In the

stabilizer of x[1] you then look for a representative r_2 that

moves x[2] to y[2]^(r_1^-1). Then the product r_2 r_1 takes x[1] to

y[1] and x[2] to y[2]. Iterate and serve.

Ignoring the time to compute a stabilizer chain this has cost $O( n l )$,

where l is the number of points in the tuples. The running time for

Leonard's method depends on the length of the orbit that G makes on the

tuples, but in the worst case the length could be $O( n ^ l )$ and the

average running time would be $O( n ^ (l/2) )$.

For the operation on sets you use backtrack. It is not so easy to

estimate the running time for this backtrack. But Leonard's method

has again a pretty bad worst case estimate.

Of course the general comment is true. My analysis was only valid under

the assumption that the operation is one of a permutation group on

points. If the length of the orbit is not bound by n or the time

to compute one image is not constant, Leonard's method will probably

be superior. However, as the above shows, for some other operations

one can do even better, if one is willing to compute a stabilizer chain.

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]