21.24 Random Methods for Permutation Groups

When permutation groups become larger, computations become slower. This increase might make it impossible to compute with these groups. The reason is mainly the creation of stabilizer chains (see StabChain): During this process a lot of schreier generators are produced for the next point stabilizer in the chain, and these generators must be processed. In actual examples, it is observed, however, that much fewer generators are needed. This observation can be justified theoretically and the random methods exploit it by using a method of the Schreier-Sims algorithm which gives the correct result with an user-given error probability.

Advantage:

:
Computations become much faster. In fact, large problems may be handled only by using random methods.

Disadvantages:

:
Computations might produce wrong results. However, you can set an error margin, which is guaranteed. The practical performance is even better than our guarantee. You should also keep in mind, that it is impossible, to eliminate system, user or programming errors.

However, there are many situations, when theory offers methods to check correctness of the results. As an example, consider the following situation. You want to compute some maximal subgroups of large sporadic groups. The ATLAS of finite groups then tells you the sizes of the groups as well as the sizes of the subgroups. The error of the random methods is one-sided in the sense that they never create strong generators which are not elements of the group. Hence if the resulting group sizes are correct, you have indeed obtained the correct result. You might also give this information to StabChain, and computation will not only be much faster, but also corresponding to the information, i.e. if you give the size, the stabilizer chain is computed correctly.

The stabilizer chain is computed using methods from BCFS91.

How to use the random methods

GAP provides the global variable StabChainOptions. This record might contain a component random. If it is set to a number i between 1 and 1000 at the beginning, random methods with guaranteed correctness frac{i}{10} percent are used (though practically the probability for correctness is much higher). This means that at all applicable places random methods will be used automatically by the same function calls. If the component is not set or set to 1000, all computations are deterministic. By standard, this component is not set, so unless you explicitely allow random computations none are used.

If the group acts on not more than a hundered points, the use of random methods has no advantage. For these groups always the deterministic methods are used.

    gap> g:=SL(4,7);
    SL(4,7)
    gap> o:=Orbit(g,[1,0,0,0]*Z(7)^0,OnLines);;Length(o);
    400
    gap> op:=Operation(g,o,OnLines);;

We create a large permutation group on 400 points. First we compute deterministic.

    gap> g:=Group(op.generators,());;
    gap> StabChain(g);;time;
    164736
    gap> Size(g);
    2317591180800

Now random methods will be used. We allow that the result is guaranteed correct only with 10 percent probability. The group is created anew.

    gap> StabChainOptions.random:=100;
    100
    gap> g:=Group(op.generators,());;
    gap> StabChain(g);;time;
    10350
    gap> Size(g);
    2317591180800

The result is still correct, though it took only less than one tenth of the time (your mileage may vary). If you give the algorithm a chance to check its results, things become even faster.

    gap> g:=Group(op.generators,());;
    gap> StabChain(g,rec(size:=2317591180800));;time;
    5054

More about random methods

When stabilizer chains are created, while random methods are allowed, it is noted in the respective groups, by setting of a record component G.stabChainOptions, which is itself a record, containg the component random. This component has the value indicated by StabChainOptions at the time the group was created. Values set in this component override the global setting of StabChainOptions. Whenever stabilizer chains are created for a group not posessing the .stabChainOptions.random entry, it is created anew from the global value StabChainOptions.

If a subgroup has no own record stabChainOptions, the one of the parent group is used instead.

As errors induced by the random functions might propagate, any (applicable) object created from the group inherits the component .stabChainOptions from the group. This applies for example to Operations and Homomorphisms.

Previous Up Top Next
Index