From: mareg@mimosa.csv.warwick.ac.uk () Subject: Re: algorithm for finding orbits Date: 23 Dec 2000 18:33:21 GMT Newsgroups: comp.theory,sci.math,comp.programming Summary: [missing] In article , "Chip Eastham" writes: > > wrote in message >news:91v9op$cfs$1@wisteria.csv.warwick.ac.uk... >> In article , >> "Chip Eastham" writes: >> > >> > wrote in message >> >news:91r2se$ilu$1@nnrp1.deja.com... >> >> I am implementing some group algorithms. Somebody pleez help me with >> >> the implementation of the following algorithm: >> >> [stuff omitted] >> >> As I pointed out in another post, the gross inefficiency here is looping >over >> all g in G rather than over a generating set of G. For example, the >> symmetric group of degree n has order n!, but can be generated by two >> permutations. >> >> Porbably the single most fundamental rule when computing with groups is to >> avoid algorithms that loop over all elements in a group like the plague. >> Always try to work with group genrators. >> >> The orbit algorithm should be structured roughly as >> >> Set O = {x}. >> for z in O >> for g in Generators(G) >> compute g(z) and if g(z) is not in O then append it to O. >> >> O is best stored as a simple list, and you would probably also store its >> characteristic function in order to test membership quickly. >> >> Derek Holt. > >Derek, > >Since the size of the orbit can equal the size of the group, I cannot >agree that a single pass through the group elements would be "gross >inefficiency". Of course if we were lucky enough to have the group >represented by generators and relations, then perhaps it is enough >to return the orbit simply by stating "generated by x" under group >action by G. OK, if the size of the orbit was equal to the order of the group then it would indeed not be such a gross inefficiency! Unfortunately, I often find that when I write something on a Newsgroup, I say things that end up sounding much stronger than I really intended! But that is one extreme. The other extreme would be size of group n!, size of orbit n, number of generators 2, and in that case I think it really would be very inefficient to loop over all group elements. But there is another problem with trying to loop over all g in G. Groups are virtually always input as generating sets, which in problems of this type are likely to be permutations or matrices. (In fact, the original poster remarked at one stage that his group was defined by generating permuations.) Performing the 'for all g in G' loop can be difficult or even impossible. Often orbit calculations are carried out as a step towards determining the order of the group - in that situation, you would not have the option of looping over all g in G. But, I agree, if it was easy to loop over all g in G, and you had reason to suspect that the orbit might be as large as the acting group, then your method would be a good one. >Recall that the original algorithm was: > >for all g in G and y in O, > compute g(y) and add it to O > >Your approach (at top) is more compact and clearer, but both should >be supplemented by at least passing reference to a check for "new" >elements of O "found" in the process of applying G or its generators >to the "old" elements of O. The process terminates once the "new" >elements portion of the list becomes empty. This bookkeeping and >logic is not needed if one makes all group elements act on only x. The following method of coding is used fairly universally in orbit algorithms. orblen := 1; orbit[1] := x; ind := 1; while ind <= orblen do pt := orbit[ind]; for g in Generators(G) fo newpt := g(pt); if not newpt in orbit then (*) orblen := orblen + 1; orbit[orblen] := newpt; end if; end for; ind := ind+1; end while; This caters very well with a wide variety of situations, and reasonably well with all situations. For a general purpose implementation, like you might find in one of the group theory packages, GAP or Magma, but also in maple and mathematica, this will serve very well. The bit that may vary from case to case is testing whether newpt is in orbit at (*). If the points being permuted are integers, then this is conveniently done by keeping a characteristic function for the orbit. But if they are something more complicated, such as vectors or subspaces being acted on by a matrix group, then a hash function could be used. >Software implementation of algorithms is rife with tradeoffs between >speed and size (either of program or of data). Even without explicit >generators or "generate and test" logic, some time-efficiency may be >obtained by using the size of the group G. > >Using a "bag" rather than a "set" collection it is possible to track the >maximum multiplicity of the orbit elements found so far, and this will >allow the algorithm to terminate once the product of the number of >elements found and the maximum multiplicity of them equals |G|. Yes that is true, and that idea can be used also with my code above. If you know the order of the group, then you can stop if orblen becomes equal to |G|. Or if you had a generator of order r and some point in the orbit fixed by that generator, then you could stop when orblen was |G|/r. Derek Holt.