GAP permits to create homomorphisms between arbitrary groups. This section considers the efficiency of the implementation and shows ways how to choose suitable representations. For permutation groups (see Permutation Groups) or Pc groups (see Pc Groups) this is normally nothing to worry about, unless the groups get extremely large. For other groups however certain calculations might be expensive and some precaution might be needed to avoid unnecessarily expensive calculations.
In short, it is always worth to tell a mapping that it is a homomorphism
(this can be done by SetIsMapping) (or to create it direcetly with
GroupHomomorphismByImagesNC).
The basic operations required are to compute image and preimage of elements and to test whether a mapping is a homomorphism. Their cost will differ depending on the type of the mapping.
Mappings given on generators (GroupHomomorphismByImages,
GroupGeneralMappingByImages)
Computing images requires to express an element of the source as word in the
generators. If it cannot be done effectivly (this is determined by
KnowsHowToDecompose, see KnowsHowToDecompose which returns true for
example for arbitrary permutation groups, for Pc groups or for finitely
presented groups with the images of the free generators) the span of the
generators has to be computed elementwise which can be very expensive and
memory consuming.
Computing preimages adheres to the same rules with swapped r^oles of generators and their images.
The test whether a mapping is a homomorphism requires
the computation of a presentation for the source and evaluation of its
relators in the images of its generators. For larger groups this can be
expensive and GroupHomomorphismByImagesNC should be used if the mapping is
known to be a homomorphism.
Action homomorphisms (ActionHomomorphism)
The calculation of images is determined by the acting function used and
-- for large domains -- is often dominated by the search for the position of
an image in a list of the domain elements. This can be improved by sorting
this list if an efficient method for < to compare elements of the domain
is available.
Once the images of a generating set are computed, computing preimages (which is
done via the AsGroupGeneralMappingByImages) and computing the kernel
bahaves the same as for a GroupHomomorphismByImages in a permutation
group.
GAP will always assume that the acting function provided implements a proper group action and thus that the mapping is indeed a homomorphism.
Mappings given by functions (GroupHomomorphismByFunction,
GroupGeneralMappingByFunctions)
Computing images is wholly determined by the function that performs the image calculation. If no function to compute preimages is given, computing preimages requires mapping every element of the source to find an element that maps to the requested image. This is time and memory consuming.
Testing whether a GroupGeneralMappingByFunctions is a homomorphism would
require mapping all products of elements and thus should be avoided.
Other operations
To compute the kernel of a homomorphism (unless the mapping is known to be injective) requires the capability to compute a presentation of the image and to evaluate the relators of this presentation in preimages of the presentations generators.
The calculation of the Image (respectively ImagesSource) requires to map
a generating set of the source, testing surjectivity is a comparison for
equality with the range.
Testing injectivity is a test for triviality of the kernel.
The comparison of mappings is based on a lexicographic comparison of a sorted element list of the source. For groups this can be simplified:
ImagesSmallestGenerators( map ) A
returns the list of images of GeneratorsSmallest(Source(map)). This
list can be used to compare group homomorphisms. (The standard
comparison is to compare the image lists on the set of elements of the
source. If however x and y have the same images under a and b,
certainly all their products have. Therefore it is sufficient to test
this on the images of the smallest generators.)
[Top] [Previous] [Up] [Next] [Index]
GAP 4 manual