<h3>9 <span class="Heading">How to write a recognition method</span></h3>
<p>This chapter explains how to integrate a newly developed group recognition method into the framework provided by the recog package.</p>
<p>TODO: Refer to Chapter <a href="chap4.html#X8058CC8187162644"><span class="RefLink">4</span></a> for an explanation of methods. There are leaf methods and split methods. The next two sections describe how to implement leaf and split methods respectively, and include example code.</p>
<p>A leaf method must at the very least do the following, examples will be provided below (TODO: add a reference):</p>
<ul>
<li><p>Provide the order of the recognized group via <code class="code">SetSize(ri, NNN)</code>.</p>
</li>
<li><p>Provide a set of SLPs which map the original generators <span class="Math">X</span> to the nice generators <span class="Math">Y</span>, as entry for the attribute <code class="code">slptonice</code>.</p>
</li>
<li><p>Provide a function which maps any element <span class="Math">g\in G</span> to a corresponding SLP in terms of the nice generators <span class="Math">Y</span>, as entry for the attribute <code class="code">slpforelement</code>.</p>
</li>
<li><p>Call <code class="code">SetFilterObj(ri, IsLeaf);</code> to mark the node as a leaf node.</p>
</li>
</ul>
<p>There are further values that can be provided, in particular to speed up computations; we'll come back to that later. Let's first look at an example: The following method is used by <strong class="pkg">recog</strong> to recognize trivial groups, as a base case for the recursive group recognition algorithm. It works for arbitrary groups.</p>
<p>TODO: AutoDoc inserts extra paragraph commands here:</p>
<div class="example"><pre>
BindRecogMethod(FindHomMethodsGeneric, "TrivialGroup", "go through generators and compare to the identity",
function(ri, G)
local gens;
# get the generators of the group
gens := GeneratorsOfGroup(G);
<P/>
# check whether all generators are trivial
# ri!.isone is explained below
if not ForAll(gens, ri!.isone) then
# NeverApplicable because it makes
# no sense to call this method again
return NeverApplicable;
fi;
<P/>
# The group is trivial! Provide required information:
<P/>
# size of the group
SetSize(ri, 1);
<P/>
# explained below
Setslpforelement(ri, SLPforElementFuncsGeneric.TrivialGroup);
<P/>
# SLP from given generators to nice generators
Setslptonice(ri, StraightLineProgramNC([[[1,0]]],
Length(gens)));
<P/>
# We have reached a leaf node.
SetFilterObj(ri, IsLeaf);
return Success;
end);
</pre></div>
<p>The input is in the format described above (TODO), and the return value is "Success".</p>
<p>Two more comments:</p>
<ul>
<li><p>When we check whether all generators are the identity, we call <code class="code">ri!.isone</code>, instead of <code class="code">IsOne</code>. The reason for this is the need to support <em>projective groups</em>. For permutation groups and matrix groups, <code class="code">ri!.isone</code> is simply defined to be <code class="code">IsOne</code>. For projective groups, it is set to <codeclass="code">IsOneProjective</code>, which can be read as "is one modulo scalars".</p>
</li>
<li><p>The function <code class="code">SLPforElementFuncs.TrivialGroup</code> takes <code class="code">ri</code> as well as an element <code class="code">g</code> as input. If <span class="Math">g \in G</span>, then it is supposed to return an SLP for <span class="Math">g</span> in terms of the nice gens <span class="Math">Y</span>. Otherwise it returns <code class="code">fail</code>. Here is the concrete implementation:</p>
</li>
</ul>
<div class="example"><pre>
SLPforElementFuncsGeneric.TrivialGroup := function(ri,g)
if not ri!.isone(g) then
return fail;
fi;
return StraightLineProgramNC( [ [1,0] ], 1 );
end;
</pre></div>
<p>Finally, we need to let <strong class="pkg">recog</strong> know about this new recognition method. This is done via the <code class="code">AddMethod</code> function. Another example!</p>
<p>TODO: refer to the <code class="code">AddMethod</code> documentation instead. Also this is outdated now. The function <code class="code">AddMethod</code> takes four mandatory arguments <codeclass="code">db</code>, <code class="code">meth</code>, <code class="code">rank</code>, <code class="code">stamp</code>, and an optional fifth argument <code class="code">comment</code>. Their meaning is as follows:</p>
<ul>
<li><p><code class="code">db</code> is the "method database", and determines to which type of groups the methods should be applied. Allowed values are:</p>
<ul>
<li><p><code class="code">meth</code> is the recognition method we have defined. In our example this is <code class="code">FindHomMethodsGeneric.TrivialGroup</code>.</p>
</li>
</ul>
<ul>
<li><p><code class="code">rank</code> is the relative rank of the recognition method, given as an integer. The idea is that methods with a high rank get called before methods with a low rank, so [recog] tries recognition methods starting from the highest rank. What the "right" rank for a given method is depends on which other methods exist and what their ranks are. As a rule of thumb, methods which are either very fast or very likely to be applicable should be tried before slower methods, or methods which are less likely to be relevant.</p>
</li>
<li><p><code class="code">stamp</code> holds a string value that uniquely describes the method. This is used for bookkeeping. It is also used in the manual, for printing the recognition tree, and for debugging purposes.</p>
</li>
<li><p><code class="code">comment</code> is a string valued comment which in the example above has been used to explain what the method does. This argument is optional and can be left out.</p>
</li>
</ul>
<p>Note that above, we only installed our method into <code class="code">FindHomDbPerm</code>. But in recog, it is actually also installed for matrix and projective groups. We reproduce the corresponding <code class="code">AddMethod</code> calls here. Note that the ranks differ, so the same method can be called with varying priority depending on the type of group.</p>
<h4>9.2 <span class="Heading">Elements with memory</span></h4>
<p>When using the memory of group elements, one currently has to always access ri!.gensHmem instead of doing <code class="code">GroupWithMemory(Grp(ri))</code>. Namely, many functions for objects with memory assume that, if the elements live in the same group, then their <code class="code">!.slp</code> components are identical.</p>
<p>Recall that splitting recognition methods produce an epimorphism <span class="Math">\phi:G\to H</span> and then delegate the work to the image <span class="Math">H</span> and the kernel <span class="Math">N:=\ker(\phi)</span>. This means that now <span class="Math">N</span> and <span class="Math">H</span> have to be constructively recognized. Such a splitting recognition method only needs to provide a homomorphism, by calling <code class="code">SetHomom(ri, hom);</code>. However, in practice one will want to provide additional data.</p>
<p>We start with an example, similar to a method used in <strong class="pkg">recog</strong>. This refers to permutation groups only!</p>
<div class="example"><pre>
BindRecogMethod(FindHomMethodsPerm, "NonTransitive", "try to find non-transitivity and restrict to orbit",
rec(validatesOrAlwaysValidInput := true),
function(ri, G)
local hom,la,o;
<P/>
# test whether we can do something:
if IsTransitive(G) then
return NeverApplicable;
fi;
<P/>
# compute orbit of the largest moved point
la := LargestMovedPoint(G);
o := Orb(G,la,OnPoints);
Enumerate(o);
# compute homomorphism into Sym(o), i.e, restrict
# the permutation action of G to the orbit o
hom := OrbActionHomomorphism(G,o);
# TODO: explanation
Setvalidatehomominput(ri, {ri,p} -> ForAll(o, x -> (x^p in o)));
# store the homomorphism into the recognition node
SetHomom(ri,hom);
<P/>
# TODO: explanation
Setimmediateverification(ri, true);
<P/>
# indicate success
return Success;
end);
</pre></div>
<p>TODO Alternatively use this:</p>
<div class="example"><pre>
FindHomMethodsPerm.NonTransitive := function(ri, G)
local hom, la, o;
# test whether we can do something:
if IsTransitive(G) then
# the action is transitive, so we can't do
# anything, and there is no point in calling us again.
return NeverApplicable;
fi;
# compute orbit of the largest moved point
la := LargestMovedPoint(G);
o := Orbit(G, la, OnPoints);
# compute homomorphism into Sym(o), i.e, restrict
# the permutation action of G to the orbit o
hom := ActionHomomorphism(G, o);
# store the homomorphism into the recognition node
SetHomom(ri, hom);
<div class="example"><pre>
FindHomMethodsMatrix.BlockLowerTriangular := function(ri, G)
# This is only used coming from a hint, we know what to do:
# A base change was done to get block lower triangular shape.
# We first do the diagonal blocks, then the lower p-part:
local H, data, hom, newgens;
# we need to construct a homomorphism, but to defined it,
# we need the image, but of course the image is defined in
# terms of the homomorphism... to break this cycle, we do
# the following: we first map the input generators using
# the helper function RECOG.HomOntoBlockDiagonal; this
# function is later also used as the underlying mapping
# of the homomorphism.
data := rec( blocks := ri!.blocks );
newgens := List(GeneratorsOfGroup(G),
x -> RECOG.HomOntoBlockDiagonal(data, x));
Assert(0, not fail in newgens);
# now that we have the images of the generators, we can
# defined the image group
H := Group(newgens);
# finally, we define the homomorphism
hom := GroupHomByFuncWithData(G, H, RECOG.HomOntoBlockDiagonal, data);
# ... and store it in the recognition node
SetHomom(ri, hom);
# since we know exactly what kind of group we are looking
# at, we don't want to run generic recognition on the
# image group and the kernel. So we provide "hints" to
# ensure more appropriate recognition methods are applied
# first.
# Give hint to image
InitialDataForImageRecogNode(ri).blocks := ri!.blocks;
Add(InitialDataForImageRecogNode(ri).hints,
rec( method := FindHomMethodsMatrix.BlockDiagonal,
rank := 2000,
stamp := "BlockDiagonal" ) );
# Tell recog that we have a better method for finding kernel
findgensNmeth(ri).method := FindKernelLowerLeftPGroup;
findgensNmeth(ri).args := [];
# Give hint to kernel N
Add(InitialDataForKernelRecogNode(ri).hints,
rec( method := FindHomMethodsMatrix.LowerLeftPGroup,
rank := 2000,
stamp := “LowerLeftPGroup" ));
InitialDataForKernelRecogNode(ri).blocks := ri!.blocks;
# This function always succeeds, because it is only
# called for inputs for which it is known to apply.
return Success;
end;
</pre></div>
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
