[Next] [Prev] [_____] [Left] [Up] [Index] [Root]
The Quotient Module Command

The Quotient Module Command

Subsections
QuotientModule(A, S) : AlgFP, AlgFP -> AlgFP
Given an fp-k-algebra A, for a field k, with r generators, and a submodule N of the free A-module of rank s specified by S, construct an A-module isomorphic to the quotient module A^s/N together with the isomorphism.

The three values returned are:

The matrices M specify a homomorphism from A to End_k(k^n), under which k^n becomes an A-module isomorphic to A^s/N. That isomorphism is given in one direction by the vectors I, which are the images in k^n of the s generators (1, 0, ..., 0), (0, 1, 0, ..., 0), ..., (0, ..., 0, 1) of A^s. In the other direction, the elements P give representatives for the images in A^s/N of the images of the n standard basis elements of k^n.

The submodule N may be specified by the parameter S in three ways:

Structuring Presentations

The relations used by the vector enumeration algorithm come from three sources:

The third group play the same role as subgroup generators in the Todd-Coxeter algorithm, and are treated specially, while the first two groups are logically equivalent, forming the relations of A in the variety of free finitely-generated associative algebras. However, when the underlying monoid of A is actually an fp-group G, the vector enumeration algorithm can use a more efficient technique to process the relations of G, and can take advantage of the fact that the generators of G are known to be invertible.

This greatly improves the performance of the algorithm, and so users are recommended to ensure as far as possible that:

Options and Controls

The QuotientModule function supports a large selection of optional arguments.

Weights

The processing of the relations of A by the vector enumeration algorithm depends on weights which are assigned to those relations (see above). The higher the weight of a relation the later it will be processed. By default, all relations are given weight 3, except those arising from relators of an fp-group, which are given weight equal to half the length of the relator.

Separate weights are used in lookahead mode, with the same default values.

QuotientModule(A, S) : AlgFP, AlgFP -> AlgFP
    MonomialWeights: [ RngIntElt ]      Default: 
    MonWts: [ RngIntElt ]               Default: 
This option sets the sequence of weights for the relations derived from the relations of the underlying monoid of A. The weights w_1, w_2, etc. are applied to the relations in the order in which they appear. If there are fewer weights than relations the remaining relations are assigned the default weight; if there are more weights than relations the extra weights are silently discarded.

Unless the MonomialLookaheadweights or MonLWts parameters are present, these weights are also used in lookahead mode.

    MonomialLookaheadWeights: [ RngIntElt ] Default: 

    MonLWts: [ RngIntElt ]              Default: 

This option sets the sequence of weights for the relations derived from the relations of the underlying monoid of A in lookahead mode only. It is otherwise similar to MonomialWeights.

    AlgebraWeights: [ RngIntElt ]       Default: 

    AlgWts: [ RngIntElt ]               Default: 

This option sets the sequence of weights for the relations given explicitly as relations of the algebra A. It is otherwise similar to MonomialWeights.

    AlgebraLookaheadWeights: [ RngIntElt ] Default: 

    AlgLWts: [ RngIntElt ]              Default: 

This option sets the sequence of weights for the relations given explicitly as relations of the algebra A in lookahead mode only. It is otherwise similar to AlgebraWeights.

Limits

Options in this group set limits on the progress of the algorithm. If the calculation cannot be performed under these constraints the value undef is returned, unless the ErrorOnFail option was set, in which case a run-time error is generated.

QuotientModule(A, S) : AlgFP, AlgFP -> AlgFP
    MaximumDimension: RngIntElt         Default: Infinity
    MaxDim: [ RngIntElt ]               Default: Infinity
This sets a limit of n on the dimension of the vector-space constructed, and on the dimension of the intermediate spaces used in the construction.

By default there is no limit, except for available memory.

    MaximumTime: FldReElt               Default: Infinity

    MaxTime: FldReElt                   Default: Infinity

This sets a limit on the CPU time available for the vector enumeration. The limit is given as a real number t and is measured in seconds.

This limit is only checked at certain points in the calculation, so it is possible for a vector enumeration to over-run, possibly by a significant amount.

By default, there is no limit.

    MaximumWeight: RngIntElt            Default: 100

    MaxWt: RngIntElt                    Default: 100

This sets a limit on the maximum weight of (basis vector, relation) pairs that will be used by the algorithm.

The weight of a basis vector is the weight of the pair that was being processed when it was defined. The weight of a pair is the weight of the basis vector plus the weight of the relation (see above).

The default limit is 100.

Logging

There are a number of options to control the level of detail provided in the informational message from the vector enumerator. When multiple contradictory options are given the first one given takes precedence.

QuotientModule(A, S) : AlgFP, AlgFP -> AlgFP
    NoLogging: BoolElt                  Default: false
    NoLog: BoolElt                      Default: false
    Silent: BoolElt                     Default: false
This option turns off all the informational messages produced by the vector enumerator.

    MaximumLogging: BoolElt             Default: false

    MaxLog: BoolElt                     Default: false

This option turns on the highest possible level of detail in the informational messages. This is too detailed for almost all purposes except debugging.

    LogActions: RngIntElt               Default: 0

    LogAct: RngIntElt                   Default: 0

This option sets the level of messages about the computation of the action of the algebra on the vector space under construction. At level 0 (the default) no messages are produced. All other levels produce copious output, with all levels above 2 being equivalent.

    LogCoincidences: RngIntElt          Default: 0

    LogCoin: RngIntElt                  Default: 0

This option sets the level of messages about the coincidences discovered and the processing of them. At level 0 (the default) no messages are produced. At level 1 every coincidence and deduction is recorded when it is discovered and when it is processed. At level 2 or higher the operation of finding the undeleted image of a vector is also recorded.

    LogInitialization: RngIntElt        Default: 0

    LogInitialisation: RngIntElt        Default: 0

    LogInit: RngIntElt                  Default: 0

This option sets the level of messages about the initialisation of new basis vectors. At level 0 (the default) no messages are produced. All other levels produce a message whenever a new basis vector is defined.

    LogPacking: RngIntElt               Default: 1

    LogPack: RngIntElt                  Default: 1

This option sets the level of messages about the reclamation of free space in the tables used by the algorithm. At level 0 no messages are produced. At level 1 (the default) it produces a message each time the pack routine is called. At level 2 or higher it records the exact renaming used to reclaim the space.

    LogPushes: RngIntElt                Default: 0

    LogPush: RngIntElt                  Default: 0

This option sets the level of messages about the pushing (or tracing) of (basis vector, relation) pairs. At level 0 (the default) it produces no messages. At level 1 a message is produced for each push that is started. At level 2 or higher the outcome of the push is also recorded.

    LogProgress: RngIntElt              Default: 0

    LogStages: RngIntElt                Default: 0

This option sets the level of messages about the overall progress of the algorithm. At level 0 no messages are produced. At level 1, simple messages are printed as the algorithm passes through its major stages. At level 2 the relations are printed as they are read in, and the complete action on the final module is printed. At level 3 or higher the action is also printed after the processing of submodule generators is complete.

    LogWeightChanges: RngIntElt         Default: 1

    LogWt: RngIntElt                    Default: 1

This option sets the level of messages about changes in the current weight (ie the weight of (basis vector, relation pairs) currently being pushed. At level 0 no such messages are produced. At level 1 (the default) or higher a message giving the new weight and the current dimension is printed.

Miscellaneous

QuotientModule(A, S) : AlgFP, AlgFP -> AlgFP
    Lookahead: BoolElt                  Default: true
This option controls whether, and to what extent, lookahead is used. If x is false then lookahead is not used. If x is true, the default, the lookahead by the default amount (two weights) is used. If x is a positive integer n then lookahead n weights is used. A sufficiently large value of n is equivalent to complete lookahead. Lookahead is commenced approximately every time the dimension doubles.

    EarlyClosing: BoolElt               Default: false

    Early: BoolElt                      Default: false

This option permits the algorithm to stop as soon as the table represents a complete action (but see below), without checking to see whether the action satisfies all the relations. In practice this action is usually correct. The default behavior is to continue and check all the relations.

    EarlyClosingMinimum: RngIntElt      Default: 

    ECMin: RngIntElt                    Default: 

This option sets a minimum dimension at which the algorithm amy stop without checking all the relators. It implies EarlyClosing.

    EarlyClosingMaximum: RngIntElt      Default: 

    ECMax: RngIntElt                    Default: 

This option sets a maximum dimension at which the algorithm amy stop without checking all the relators. It implies EarlyClosing.

    ConstructMorphism: BoolElt          Default: true

    Morphism: BoolElt                   Default: true

This option controls whether the third return value of the QuotientModule function is in fact computed. A small overhead of time and space is required to compute it, and many applications do not need it, so this option is provided. When b is true (the default) the third return value is computed, when b is false it is not.

    ErrorOnFail: BoolElt                Default: 

    ErrFail: BoolElt                    Default: 

This option controls the behaviour of the program if there is insufficient time or space to complete the calculation, or if the calculation has not been completed when the maximum weight is reached. If it is present a run-time error is generated, otherwise the value undef is returned.


Example AlgFP_PermutationActionD8 (H52E3)

First we repeat the examples above, in Magma. The permutation action of D_8

> d8<a,b> := Group<a,b | a^ 4 = b^ 2 = (a*b)^ 2 = 1>;
> q := RationalField();
> a1<a,b> := FreeAlgebra(q,d8);
> i1 := rideal<a1 | b-1 >;
> mats, im, preim := QuotientModule(a1,i1);
Read Input
Done submodule generators
Starting weight 2 in define mode, 1 alive out of 2
Starting weight 3 in define mode, 1 alive out of 2
Looking ahead ...
Starting weight 4 in lookahead mode, 4 alive out of 5
Starting weight 5 in lookahead mode, 4 alive out of 5
    ...done
Packing 5 to 4
Starting weight 4 in define mode, 4 alive out of 4
Starting weight 5 in define mode, 4 alive out of 4
Starting weight 6 in define mode, 4 alive out of 4
Starting weight 7 in define mode, 5 alive out of 6
Starting weight 8 in define mode, 6 alive out of 7
Starting weight 9 in define mode, 4 alive out of 7
Starting weight 10 in define mode, 4 alive out of 7
Closed, 7 rows defined
Packing 7 to 4
4 live dimensions
Successful
>  print mats;
[
    [0 0 1 0]
    [1 0 0 0]
    [0 0 0 1]
    [0 1 0 0],

[1 0 0 0] [0 0 1 0] [0 1 0 0] [0 0 0 1] ] > im; [ (1 0 0 0) ] > preim; [ Id(), a^ -1, a^ -1 * b, a^ -2 ] >


Example AlgFP_Quotient (H52E4)

A quotient of that module.

We continue from the last example and set:

> d8<a,b> := Group<a,b | a^ 4 = b^ 2 = (a*b)^ 2 = 1>;
> q := RationalField();
> a1<a,b> := FreeAlgebra(q,d8);
> i2 := rideal<a1 | b-1, 1+a^ 3+a^ 3*b+a^ 2>; 
> mats, im, preim := QuotientModule(a1,i2);
Read Input
Done submodule generators
Starting weight 2 in define mode, 4 alive out of 6
Starting weight 3 in define mode, 5 alive out of 7
Starting weight 4 in define mode, 3 alive out of 7
Starting weight 5 in define mode, 3 alive out of 7
Closed, 7 rows defined
Packing 7 to 3
3 live dimensions
Successful
>  print mats;
[
    [ 0  1  0]
    [ 0  0  1]
    [-1 -1 -1],

[ 1 0 0] [-1 -1 -1] [ 0 0 1] ]

[Next] [Prev] [_____] [Left] [Up] [Index] [Root]