For most computations with permutation groups, it is crucial to construct stabilizer chains efficiently. Sims's original construction Sim70 is deterministic, and is called the Schreier-Sims algorithm, because it is based on Schreier's Lemma (p. 96 in Hall): given K = áS ñ and a transversal T for K mod L, one can obtain |S||T| generators for L. This lemma is applied recursively, with consecutive point stabilizers G(i) and G(i+1) playing the role of K and L.
In permutation groups of large degree, the number of Schreier generators to be processed becomes too large, and the deterministic Schreier-Sims algorithm becomes impractical. Therefore, GAP uses randomized algorithms. The method selection process, which is quite different from Version 3, works the following way.
If a group acts on not more than a hundred points,
Sims's original deterministic algorithm is applied. In groups of
degree greater than hundred, a heuristic algorithm based
on ideas in BCFS91 constructs a stabilizer chain.
This construction is complemented by a
verify-routine that either proves the correctness of the stabilizer chain
or causes the extension of the chain to a correct one.
The user can influence the verification process by setting
the value of the record component random
(cf. Construction of Stabilizer Chains).
If random = 1000 then a slight extension of an unpublished method of
Sims is used. The outcome of this verification process is always
correct. The user also can prescribe any integer 1 £ x £ 999
as the value of random. In this case, a randomized verification
process from BCFS91 is applied, and the result of the
stabilizer chain construction is guaranteed to be correct with probability
at least x/1000. The practical performance of the algorithm is
much better than the theoretical guarantee.
If the stabilizer chain is not correct then the elements in the
product of transversals R(m)R(m-1)¼R(1) constitute a
proper subset of the group G in question.
This means that a membership test with this stabilizer chain
returns false for
all elements that are not in G,
but it may also return false for some elements of G;
in other words, the result true of a membership test is always correct,
whereas the result false may be incorrect.
The construction and verification phases are separated because
there are situations where the verification step can be omitted;
if one happens to know the order of the group in advance then the
randomized construction of the stabilizer chain stops
as soon as the product of the lengths of the basic orbits
of the chain equals the group order, and the chain will be correct
(see the size option of the StabChain command in StabChain).
Although the worst case running time is roughly quadratic for
Sims's verification and roughly linear for the randomized one,
in most examples the running time of the stabilizer chain
construction with random = 1000 (i.e., guaranteed correct output)
is about the same as the running time of randomized verification
with guarantee of at least 90% correctness. Therefore, we suggest
to use the default value random = 1000. Possible uses of
random < 1000 are when one has to run through a large collection
of subgroups, and a low value of random is used to choose quickly
a candidate for more thorough examination; another use is when
the user suspects that the quadratic bottleneck of the guaranteed
correct verification is hit.
We will illustrate these ideas in two examples.
gap> h:= SL(4,7);; gap> o:= Orbit( h, [1,0,0,0]*Z(7)^0, OnLines );; gap> op:= Action( h, o, OnLines );; gap> NrMovedPoints( op ); 400
We created a permutation group on 400 points.
First we compute a guaranteed correct stabilizer chain.
(The StabChain command is described in StabChain.)
gap> h:= Group( GeneratorsOfGroup( op ) );; gap> StabChain( h );; time; 1120 gap> Size( h ); 2317591180800
Now randomized verification will be used.
We require that the result is guaranteed correct with probability 90%.
This means that if we would do this calculation many times over,
GAP would guarantee that in least 90% percent of all calculations
the result is correct.
In fact the results are much better than the guarantee,
but we cannot promise that this will really happen.
(For the meaning of the random component in the second argument of
StabChain, see StabChain.)
First the group is created anew.
gap> h:= Group( GeneratorsOfGroup( op ) );; gap> StabChain( h, rec( random:= 900 ) );; time; 1410 gap> Size( h ); 2317591180800
The result is still correct, and the running time is actually somewhat slower. If you give the algorithm additional information so that it can check its results, things become faster and the result is guaranteed to be correct.
gap> h:=Group( GeneratorsOfGroup( op ) );; gap> SetSize( h, 2317591180800 ); gap> StabChain( h );; time; 170
The second example gives a typical group when the verification
with random = 1000 is slow. The problem is that the group
has a stabilizer subgroup G(i) such that the fundamental
orbit O(i) is split into a lot of orbits when we stabilize
bi and one additional point of O(i).
gap> p1:=PermList(Concatenation([401],[1..400]));; gap> p2:=PermList(List([1..400],i->(i*20 mod 401)));; gap> d:=DirectProduct(Group(p1,p2),SymmetricGroup(5));; gap> h:=Group(GeneratorsOfGroup(d));; gap> StabChain(h);;time;Size(h); 1030 192480 gap> h:=Group(GeneratorsOfGroup(d));; gap> StabChain(h,rec(random:=900));;time;Size(h); 570 192480
When stabilizer chains of a group G are created
with random < 1000, this is noted in the group G,
by setting of the record component random
in the value of the attribute StabChainOptions for G
(see StabChainOptions).
As errors induced by the random methods might propagate,
any group or homomorphism created from G inherits a random component
in its StabChainOptions from the corresponding component for G.
A lot of algorithms dealing with permutation groups use randomized methods; however, if the initial stabilizer chain construction for a group is correct, these further methods will provide guaranteed correct output.
[Top] [Previous] [Up] [Next] [Index]
GAP 4 manual