4 Options for ACE

introduced in version 3.001 of the ACE Package to perform the same function, is now a synonym for ResetOptionsStack; it simply executes PopOptions() until OptionsStack is empty.

However, ResetOptionsStack (or FlushOptionsStack) does not wipe out the options already passed to an interactive ACE process. We have provided GetACEOptions (see GetACEOptions) to keep track of options that the ACE binary process still considers active, which may or may not be still on the OptionsStack. There is the interactive SetACEOptions (see SetACEOptions) to change such options, or, of course, you can always elect to use ACEQuit (see ACEQuit) and then start a new interactive ACE process.

Finally, if ACEIgnoreUnknownDefault := false (see ACEIgnoreUnknownDefault), there will be situations where an ACE interface function needs to be told explicitly to ignore options passed down recursively to it from calling functions. For this purpose we have provided the options aceignore (see option aceignore) and aceignoreunknown (see option aceignoreunknown).

4.3 Abbreviations and mixed case for ACE Options

Except for limitations imposed by GAP e.g. clashes with GAP keywords and blank spaces not allowed in keywords, the options of the ACE interface are the same as for the binary; so, for example, the options can appear in upper or lower case (or indeed, mixed case) and most may be abbreviated. Below we only list the options in all lower case, and in their longest form; where abbreviation is possible we give the shortest abbreviation in the option's description e.g. for the mendelsohn option we state that its shortest abbreviation is mend, which means mende, mendel etc., and indeed, Mend and MeND, are all valid abbreviations of that option. Some options have synonyms e.g. cfactor is an alternative for ct.

The complete list of ACE options known to the ACE interface functions, their abbreviations and the values that they are known to take may be gleaned from the KnownACEOptions record (see Section The KnownACEOptions Record).

Options for each of the ACE interface functions ACECosetTableFromGensAndRels, ACECosetTable, ACEStats and ACEStart (see Chapter Functions for Using ACE Interactively), comprise the few non-ACE-binary options (silent, aceinfile, aceoutfile, aceignore, aceignoreunknown, acenowarnings, aceincomment, aceecho and echo) discussed in Section Non-ACE-binary Options, (almost) all single-word ACE binary options and purer and purec. The options purer and purec give the ACE binary options pure r and pure c, respectively; (they are the only multiple-word ACE binary options that do not have a single word alternative). The only single-word ACE binary options that are not available via the ACE interface are abbreviations that clash with GAP keywords (e.g. fi for fill, rec for recover and continu for continue). The detail of this paragraph is probably of little importance to the GAP user; these comments have been included for the user who wishes to reconcile the respective functionalities of the ACE interface and the ACE standalone, and are probably of most value to standalone users.

4.4 Honouring of the order in which ACE Options are passed

Note: Below we describe the intended behaviour, but unfortunately, since GAP 4.5 (approximately when ACE 5.1 was released) the order of options behind the colon is no longer honoured. Until this is fixed, if the order of ACE options needs to be respected, users should use ACE interactively (see ACEStart).

It is important to realize that ACE's options (even the non-strategy options) are not orthogonal, i.e. the order in which they are put to ACE can be important. For this reason, except for a few options that have no effect on the course of an enumeration, the order in which options are passed to the ACE interface is preserved when those same options are passed to the ACE binary. One of the reasons for the non-orthogonality of options is to protect the user from obtaining invalid enumerations from bad combinations of options; another reason is that commonly one may specify a strategy option and override some of that strategy's defaults; the general rule is that the later option prevails. By the way, it's not illegal to select more than one strategy, but it's not sensible; as just mentioned, the later one prevails.

4.5 What happens if no ACE Strategy Option or if no ACE Option is passed

If an ACE interface function (ACECosetTableFromGensAndRels, ACEStats, ACECosetTable or ACEStart) is given no strategy option, the default strategy (see Chapter Strategy Options for ACE) is selected, and a number of options that ACE needs to have a value for are given default values, prior to the execution of any user options, if any. This ensures that ACE has a value for all its ``run parameters''; three of these are defined from the ACE interface function arguments; and the remaining ``run parameters'', we denote by ``ACE Parameter Options''. For user convenience, we have provided the ACEParameterOptions record (see ACEParameterOptions), the fields of which are the ``ACE Parameter Options''. The value of each field (option) of the ACEParameterOptions record is either a default value or (in the case of an option that is set by a strategy) a record of default values that ACE assumes when the user does not define a value for the option (either indirectly by selecting a strategy option or directly).

If the default strategy does not suffice, most usually a user will select one of the other strategies from among the ones listed in Chapter Strategy Options for ACE, and possibly modify some of the options by selecting from the options in this chapter. It's not illegal to select more than one strategy, but it's not sensible; as mentioned above, the later one prevails.

4.6 Interpretation of ACE Options

Options may be given a value by an assignment to the name (such as time := val); or be passed without assigning a value, in which case GAP treats the option as boolean and sets the option to the value true, which is then interpreted by the ACE interface functions. Technically speaking the ACE binary itself does not have boolean options, though it does have some options which are declared by passing without a value (e.g. the hard strategy option) and others that are boolean in the C-sense (taking on just the values 0 or 1). The behaviour of the ACE interface functions (ACECosetTableFromGensAndRels, ACEStats, ACECosetTable or ACEStart) is essentially to restore as much as is possible a behaviour that mimics the ACE standalone; a false value is always translated to 0 and true may be translated to any of no-value, 0 or 1. Any option passed with an assigned value val other than false or true is passed with the value val to the ACE binary. Since this may appear confusing, let's consider some examples.

• The hard strategy option (see option hard) should be passed without a value, which in turn is passed to the ACE binary without a value. However, the ACE interface function cannot distinguish the option hard being passed without a value, from it being passed via hard := true. Passing hard := false or hard := val for any non-true val will however produce a warning message (unless the option acenowarnings is passed) that the value 0 (for false) or val is unknown for that option. Nevertheless, despite the warning, in this event, the ACE interface function passes the value to the ACE binary. When the ACE binary sees a line that it doesn't understand it prints a warning and simply ignores it. (So passing hard := false will produce warnings, but will have no ill effects.) The reason we still pass unknown values to the ACE binary is that it's conceivable a future version of the ACE binary might have several hard strategies, in which case the ACE interface function will still complain (until it's made aware of the new possible values) but it will perform in the correct manner if a value expected by the ACE binary is passed.

• The felsch strategy option (see option felsch) may be passed without a value (which chooses the felsch 0 strategy) or with the values 0 or 1. Despite the fact that GAP sees this option as boolean; it is not. There are two Felsch strategies: felsch 0 and felsch 1. To get the felsch 1 strategy, the user must pass felsch := 1. If the user were to pass felsch := false the result would be the felsch 0 strategy (since false is always translated to 0), i.e. the same as how felsch := true would be interpreted. We could protect the user more from such ideosyncrasies, but we have erred on the side of simplicity in order to make the interface less vulnerable to upgrades of the ACE binary.

The lesson from the two examples is: check the documentation for an option to see how it will be interpreted. In general, options documented (in this chapter) as only being no-value options can be safely thought of as boolean (i.e. you will get what you expect by assigning true or false), whereas strategy (no-value) options should not be thought of as boolean (a false assignment will not give you what you might have expected).

Options that are unknown to the ACE interface functions and not ignored (see below), that are passed without a value, are always passed to the ACE binary as no-value options (except when the options are ignored); the user can over-ride this behaviour simply by assigning the intended value. Note that it is perfectly safe to allow the ACE binary to be passed unknown options, since ACE simply ignores options it doesn't understand, issues an error message (which is just a warning and is output by GAP unless acenowarnings (see option acenowarnings) is passed) and continues on with any other options passed in exactly the way it would have if the ``unknown'' options had not been passed.

An option is ignored if it is unknown to the ACE interface functions and one of the following is true:

• the global variable ACEIgnoreUnknownDefault is set to false (see ACEIgnoreUnknownDefault) or,

• the aceignoreunknown option (see option aceignoreunknown) is passed, or

• the aceignore option is passed and the option is an element of the list value of aceignore (see option aceignore).

It is actually recommended that the user set ACEIgnoreUnknownDefault to false, since this will allow the user to see when ACE functions have been passed options that are ``unknown'' to the ACE package. In this way the user will be informed about misspelt options, for example. So it's a good debugging tool. Also, if the ACE binary is updated with a version with new options then these will not be known by the package (the GAP part) and it will be necessary to set ACEIgnoreUnknownDefault to false in order for the new options to be passed to the binary. When an ACE function is invoked indirectly by some function that was called with non-ACE options the warning messages may begin to be annoying, and it's then a simple matter to set ACEIgnoreUnknownDefault back to the ACE 3.003 default value of true.

Warning messages regarding unknown options are printed unless the acenowarnings (see option acenowarnings) is passed or the option is ignored.

To see how options are interpreted by an ACE interface function, pass the echo option.

As mentioned above, any option that the ACE binary doesn't understand is simply ignored and a warning appears in the output from ACE. If this occurs, you may wish to check the input fed to ACE and the output from ACE, which when ACE is run non-interactively are stored in files whose full path names are recorded in the record fields ACEData.infile and ACEData.outfile, respectively. Alternatively, both interactively and non-interactively one can set the InfoLevel of InfoACE to 3 (see SetInfoACELevel), to see the output from ACE, or to 4 to also see the commands directed to ACE.

4.7 An Example of passing Options

Continuing with the example of Section Using ACE Directly to Generate a Coset Table, one could set the echo option to be true, use the hard strategy option, increase the workspace to 10⁷ words and turn messaging on (but to be fairly infrequent) by setting messages to a large positive value as follows:

gap> ACECosetTable(fgens, rels, [c]
>                  : echo, hard, Wo := 10^7, mess := 10000);;

As mentioned in the previous section, echo may be thought of as a boolean option, whereas hard is a strategy option (and hence should be thought of as a no-value option). Also, observe that two options have been abbreviated: Wo is a mixed case abbreviation of workspace, and mess is an abbreviation of messages.

4.8 The KnownACEOptions Record

is a GAP record whose fields are the ACE options known to the ACE interface; each field (known ACE option) is assigned to a list of the form [i, ListOrFunction], where i is an integer representing the length of the shortest abbreviation of the option and ListOrFunction is either a list of (known) allowed values or a boolean function that may be used to determine if the given value is a (known) valid value e.g.

gap> KnownACEOptions.compaction;
[ 3, [ 0 .. 100 ] ]

indicates that the option compaction may be abbreviated to com and the (known) valid values are in the (integer) range 0 to 100; and

gap> KnownACEOptions.ct;
[ 2, <Category "IsInt"> ]

indicates that there is essentially no abbreviation of ct (since its shortest abbreviation is of length 2), and a value of ct is known to be valid if IsInt returns true for that value.

For user convenience, we provide the function

which for a string optname representing an ACE option (or a guess of one) returns a record with the following fields:

 name

optname (unchanged);

 known

true if optname is a valid mixed case abbreviation of a known ACE option, and false otherwise;

 fullname

the lower case unabbreviated form of optname if the known field is set true, or optname in all lower case, otherwise;

 synonyms

a list of known ACE options synonymous with optname, in lowercase unabbreviated form, if the known field is set true, or a list containing just optname in all lower case, otherwise;

 abbrev

the shortest lowercase abbreviation of optname if the known field is set true, or optname in all lower case, otherwise.

For more on synonyms of ACE options, see ACEOptionSynonyms.

The function ACEOptionData provides the user with all the query facility she should ever need; nevertheless, we provide the following functions.

returns true if optname is a mixed case abbreviation of a field of KnownACEOptions, or false otherwise. IsKnownACEOption(optname); is equivalent to

ACEOptionData(optname).known;

returns the lowercase unabbreviated first alternative of optname if it is a known ACE option, or optname in lowercase, otherwise. ACEPreferredOptionName(optname); is equivalent to

ACEOptionData(optname).synonyms[1];

returns true if optname is an ``ACE parameter option''. (ACE Parameter Options are described in Section ACEParameterOptions). IsACEParameterOption(optname); is equivalent to

ACEPreferredOptionName(optname) in RecNames(ACEParameterOptions);

returns true if optname is an ``ACE strategy option'' (see Section The ACEStrategyOptions list). IsACEStrategyOption(optname); is equivalent to

ACEPreferredOptionName(optname) in ACEStrategyOptions;

4.9 The ACEStrategyOptions List

is a GAP list that contains the strategy options known to the ACE interface functions:

gap> ACEStrategyOptions;
[ "default", "easy", "felsch", "hard", "hlt", "purec", "purer", "sims" ]

See Chapter Strategy Options for ACE for details regarding the ACE strategy options.

4.10 ACE Option Synonyms

is a GAP record. A number of known ACE options have synonyms. The fields of the ACEOptionSynonyms record are the ``preferred'' option names and the values assigned to the fields are the lists of synonyms of those option names. What makes an option name ``preferred'' is somewhat arbitrary (in most cases, it is simply the shortest of a list of synonyms). For a ``preferred'' option name optname that has synonyms, the complete list of synonyms may be obtained by concatenating [ optname ] and ACEOptionSynonyms.(optname), e.g.

gap> Concatenation( [ "messages" ], ACEOptionSynonyms.("messages") );
[ "messages", "monitor" ]

More generally, for an arbitrary option name optname its list of synonyms (which may be a list of one element) may be obtained as the synonyms field of the record returned by ACEOptionData(optname) (see ACEOptionData).

4.11 Non-ACE-binary Options

is a GAP list of options that have meaning only for the ACE Package interface, i.e. options in KnownACEOptions that are not ACE binary options; each such option is described in detail below. Except for the options listed in NonACEbinOptions and those options that are excluded via the aceignore and aceignoreunknown options (described below), all options that are on the OptionsStack when an ACE interface function is called, are passed to the ACE binary. Even options that produce the warning message: ``unknown (maybe new) or bad'', by virtue of not being a field of KnownACEOptions, are passed to the ACE binary (except that the options purer and purec are first translated to pure r and pure c, respectively). When the ACE binary encounters an option that it doesn't understand it issues a warning and simply ignores it; so options accidentally passed to ACE are unlikely to pose problems.

We also mention here, since it is related to an option of this section, the following.

is a global variable (not an option) that is initially set by the ACE package to true, and is the default action that ACE takes for options that are unknown to the ACE package (but may be new options provided in a new version of the ACE binary). Despite the fact that it is normally set true, it is recommended (especially for the novice user of the ACE package) to set ACEIgnoreUnknownDefault := false; the worst that can happen is being annoyed by a profusion of warnings of unknown options. For individual functions, the user may use the option aceignoreunknown (see option aceignoreunknown) to over-ride the setting of ACEIgnoreUnknownDefault.

Here now, are the few options that are available to the GAP interface to ACE that have no counterpart in the ACE standalone:

silent

Inhibits an Error return when generating a coset table.

If a coset enumeration that invokes ACECosetTableFromGensAndRels does not finish within the preset limits, an error is raised by the interface to GAP, unless the option silent or incomplete (see option incomplete) has been set; in the former case, fail is returned. This option is included to make the behaviour of ACECosetTableFromGensAndRels compatible with that of the function CosetTableFromGensAndRels it replaces. If the option incomplete is also set, it overrides option silent.

lenlex

Ensures that ACECosetTable and ACECosetTableFromGensAndRels output a coset table that is lenlex standardised.

The lenlex scheme, numbers cosets in such a way that their ``preferred'' (coset) representatives, in an alphabet consisting of the user-submitted generators and their inverses, are ordered first according to length and then according to a lexical ordering. In order to describe what the lenlex scheme's lexical ordering is, let us consider an example. Suppose the generators submitted by the user are, in user-supplied order, [x, y, a, b], and represent the inverses of these generators by the corresponding uppercase letters: [X, Y, A, B], then the lexical ordering of lenlex is that derived from defining x < X < y < Y < a < A < b < B.

Notes: In some circumstances, ACE prefers to swap the first two generators; such cases are detected by the function IsACEGeneratorsInPreferredOrder (see IsACEGeneratorsInPreferredOrder). In such cases, special action is taken to avoid ACE swapping the first two generators; this action is described in the notes for ACEStandardCosetNumbering (see ACEStandardCosetNumbering). When this special action is invoked, a side-effect is that any setting of the asis (see option asis) option by the user is ignored.

The lenlex standardisation scheme is the default coset table standardisation scheme of GAP. Alternatively, semilenlex can be used. Both schemes are described in detail in Section Coset Table Standardisation Schemes.

semilenlex

Ensures that ACECosetTable and ACECosetTableFromGensAndRels output a coset table that is semilenlex standardised.

The semilenlex scheme, numbers cosets in such a way that their ``preferred'' (coset) representatives, in an alphabet consisting of only the user-submitted generators, are ordered first according to length and then according to a lexical ordering.

incomplete

Allows the return of an incomplete coset table, when a coset enumeration does not finish within preset limits.

If a coset enumeration that invokes ACECosetTableFromGensAndRels or ACECosetTable does not finish within the preset limits, an error is raised by the interface to GAP, unless the option silent (see option silent) or incomplete has been set; in the latter case, a partial coset table, that is a valid GAP list of lists, is returned. Each position of the table without a valid coset number entry is filled with a zero. If the option silent is also set, incomplete prevails. An incomplete table is returned reduced (i.e. with insignificant coset numbers --- those appearing only in their place of definition --- removed) and lenlex standardised (regardless of whether the semilenlex option is in force). When an incomplete table is returned, a warning is emitted at InfoACE or InfoWarning level 1.

aceinfile:=filename

Creates an ACE input file filename for use with the standalone only; filename should be a string. (Shortest abbreviation: acein.)

This option is only relevant to ACECosetTableFromGensAndRels and is ignored if included as an option for invocations of ACEStats and ACEStart. If this option is used, GAP creates an input file with filename filename only, and then exits (i.e. the ACE binary is not called). This option is provided for users who wish to work directly with the ACE standalone. The full path to the input file normally used by ACE (i.e. when option aceinfile is not used) is stored in ACEData.infile.

aceoutfile:=filename

Redirects ACE output to file filename; filename should be a string. (Shortest abbreviation: aceo.)

This is actually a synonym for the ao option. Please refer to option ao, for further discussion of this option.

aceignore:=optionList

Directs an ACE function to ignore the options in optionList; optionList should be a list of strings. (Shortest abbreviation: aceig.)

If a function called with its own options, in turn calls an ACE function for which those options are not intended, the ACE function will pass those options to the ACE binary. If those options are unknown to the ACE interface (and ACEIgnoreUnknownDefault := false and aceignoreunknown is not passed; see ACEIgnoreUnknownDefault and option aceignoreunknown) a warning is issued. Options that are unknown to the ACE binary are simply ignored by ACE (and a warning that the option was ignored appears in the ACE output, which the user will not see unless the InfoLevel of InfoACE or InfoWarning is set to 1). This option enables the user to avoid such options being passed at all, thus avoiding the warning messages and also any options that coincidentally are ACE options but are not intended for the ACE function being called.

aceignoreunknown

Directs an ACE function to ignore any options not known to the ACE interface. (Shortest abbreviation: aceignoreu.)

This option is provided for similar reasons to aceignore. Normally, it is safe to include it, to avoid aberrant warning messages from the ACE interface. However, fairly obviously, it should not be passed without a value (or set to true) in the situation where a new ACE binary has been installed with new options that are not listed among the fields of KnownACEOptions, which you intend to use. Omitting the aceignoreunknown option is equivalent to setting it to the value of ACEIgnoreUnknownDefault (see ACEIgnoreUnknownDefault); i.e. it is superfluous if ACEIgnoreUnknownDefault := true unless aceignoreunknown is set to false.

acenowarnings

Inhibits the warning message ``unknown (maybe new) or bad option'' for options not listed in KnownACEOptions. (Shortest abbreviation: acenow.)

This option suppresses the warning messages for unknown options (to the ACE interface), but unlike aceignore and aceignoreunknown still allows them to be passed to the ACE binary.

echo

echo:=2

Echoes arguments and options (and indicates how options were handled).

Unlike the previous options of this section, there is an ACE binary option echo. However, the echo option is handled by the ACE interface and is not passed to the ACE binary. (If you wish to put echo in a standalone script use the aceecho option following.) If echo is passed with the value 2 then a list of the options (together with their values) that are set via ACE defaults are also echoed to the screen.

aceecho

The ACE binary's echo command.

This option is only included so that a user can put an echo statement in an ACE standalone script. Otherwise, use echo (above).

aceincomment:=string

Print comment string in the ACE input; string must be a string. (Shortest abbreviation: aceinc.)

This option prints the comment string behind a sharp sign (#) in the input to ACE. Only useful for adding comments (that ACE ignores) to standalone input files.

aceexampleoptions

An internal option for ACEExample.

This option is passed internally by ACEExample to the ACE interface function it calls, when one invokes ACEExample with options. Its purpose is to provide a mechanism for the over-riding of an example's options by the user. The option name is deliberately long and has no abbreviation to discourage user use.

4.12 ACE Parameter Options

is a GAP record, whose fields are the ``ACE Parameter Options''. The ``ACE Parameter Options'' are options which, if not supplied a value by the user, are supplied a default value by ACE. In fact, the ``ACE Parameter Options'' are those options that appear (along with Group Generators, Group Relators and Subgroup Generators, which are defined from ACE interface function arguments) in the ``Run Parameters'' block of ACE output, when, for example, the messages option is non-zero.

For each field (ACE parameter option) of the ACEParameterOptions record, the value assigned is the default value (or a record of default values) that are supplied by ACE when the option is not given a value by the user (either indirectly by selecting a strategy option or directly).

In the cases where the value of a field of the ACEParameterOptions record is itself a record, the fields of that record are default and strategies for which the value assigned by that strategy differs from the default strategy. A ``strategy'', here, is the strategy option itself, if it is only a no-value option, or the strategy option concatenated with any of its integer values (as strings), otherwise (e.g. felsch0 and sims9 are strategies, and hlt is both a strategy and a strategy option). As an exercise, the reader might like to try to reproduce the table at the beginning of Chapter Strategy Options for ACE using the ACEParameterOptions record. (Hint: you first need to select those fields of the ACEParameterOptions record whose values are records with at least two fields.)

Note: Where an ``ACE Parameter Option'' has synonyms, only the ``preferred'' option name (see ACEOptionSynonyms) appears as a field of ACEParameterOptions. The complete list of ``ACE Parameter Options'' may be obtained by

gap> Concatenation( List(RecNames(ACEParameterOptions),
>                        optname -> ACEOptionData(optname).synonyms) );
[ "path", "subgroup", "max", "time", "fill", "ffactor", "asis", "ct", 
  "cfactor", "compaction", "dmode", "dsize", "enumeration", "hole", 
  "lookahead", "loop", "mendelsohn", "messages", "monitor", "no", "pmode", 
  "psize", "rt", "rfactor", "row", "workspace" ]

We describe the ``ACE Parameter Options'' in the Sections General ACE Parameter Options that Modify the Enumeration Process, ACE Parameter Options Modifying C Style Definitions, ACE Parameter Options for R Style Definitions, ACE Parameter Options for Deduction Handling, Technical ACE Parameter Options, ACE Parameter Options controlling ACE Output, and ACE Parameter Options that give Names to the Group and Subgroup, following.

4.13 General ACE Parameter Options that Modify the Enumeration Process

asis

Do not reduce relators. (Shortest abbreviation: as.)

By default, ACE freely and cyclically reduces the relators, freely reduces the subgroup generators, and sorts relators and subgroup generators in length-increasing order. If you do not want this, you can switch it off by setting the asis option.

Notes: As well as allowing you to use the presentation as it is given, this is useful for forcing definitions to be made in a prespecified order, by introducing dummy (i.e., freely trivial) subgroup generators. (Note that the exact form of the presentation can have a significant impact on the enumeration statistics.) For some fine points of the influence of asis being set on the treatment of involutory generators see the ACE standalone manual.

ct:=val

cfactor:=val

Number of C style definitions per pass; val should be an integer. (Shortest abbreviation of cfactor is c.)

The absolute value of val sets the number of C style definitions per pass through the enumerator's main loop. The sign of val sets the style. The possible combinations of the values of ct and rt (described below) are given in the table of enumeration styles in Section Enumeration Style.

rt:=val

rfactor:=val

Number of R style definitions per pass; val should be an integer. (Shortest abbreviation of rfactor is r.)

The absolute value of val sets the number of R style definitions per pass through the enumerator's main loop. The sign of val sets the style. The possible combinations of the values of ct (described above) and rt are given in the table of enumeration styles in Section Enumeration Style.

no:=val

The number of group relators to include in the subgroup; val should be an integer greater than or equal to −1.

It is sometimes helpful to include the group relators into the list of the subgroup generators, in the sense that they are applied to coset number 1 at the start of an enumeration. A value of 0 for this option turns this feature off and the (default) argument of −1 includes all the relators. A positive argument includes the specified number of relators, in order. The no option affects only the C style procedures.

mendelsohn

Turns on mendelsohn processing. (Shortest abbreviation: mend.)

Mendelsohn style processing during relator scanning/closing is turned on by giving this option. Off is the default, and here relators are scanned only from the start (and end) of a relator. Mendelsohn ``on'' means that all (different) cyclic permutations of a relator are scanned.

The effect of Mendelsohn style processing is case-specific. It can mean the difference between success or failure, or it can impact the number of coset numbers required, or it can have no effect on an enumeration's statistics.

Note: Processing all cyclic permutations of the relators can be very time-consuming, especially if the presentation is large. So, all other things being equal, the Mendelsohn flag should normally be left off.

4.14 ACE Parameter Options Modifying C Style Definitions

The next three options are relevant only for making C style definitions (see Section Enumeration Style). Making definitions in C style, that is filling the coset table line by line, it can be very advantageous to switch to making definitions from the preferred definition stack. Possible definitions can be extracted from this stack in various ways and the two options pmode and psize (see option pmode and option psize respectively) regulate this. However it should be clearly understood that making all definitions from a preferred definition stack one may violate the condition of Mendelsohn's theorem, and the option fill (see option fill) can be used to avoid this.

fill:=val

ffactor:=val

Controls the preferred definition strategy by setting the fill factor; val must be a non-negative integer. (Shortest abbreviation of fill is fil, and shortest abbreviation of ffactor is f.)

Unless prevented by the fill factor, gaps of length one found during deduction testing are preferentially filled (see Hav91). However, this potentially violates the formal requirement that all rows in the coset table are eventually filled (and tested against the relators). The fill factor is used to ensure that some constant proportion of the coset table is always kept filled. Before defining a coset number to fill a gap of length one, the enumerator checks whether fill times the completed part of the table is at least the total size of the table and, if not, fills coset table rows in standard order (i.e. C style; see Section Enumeration Style) instead of filling gaps.

An argument of 0 selects the default value of ⎣5(n+2)/4 ⎦, where n is the number of columns in the table. This default fill factor allows a moderate amount of gap-filling. If fill is 1, then there is no gap-filling. A large value of fill can cause what is in effect infinite looping (resolved by the coset enumeration failing). However, in general, a large value does work well. The effects of the various gap-filling strategies vary widely. It is not clear which values are good general defaults or, indeed, whether any strategy is always ``not too bad''.

This option is identified as Fi in the ``Run Parameters'' block (obtained when messages is non-zero) of the ACE output, since for the ACE binary, fi is an allowed abbreviation of fill. However, fi is a GAP keyword and so the shortest abbreviation of fill allowed by the interface functions is fil.

pmode:=val

Option for preferred definitions; val should be in the integer range 0 to 3. (Shortest abbreviation: pmod.)

The value of the pmode option determines which definitions are preferred. If the argument is 0, then Felsch style definitions are made using the next empty table slot. If the argument is non-zero, then gaps of length one found during relator scans in Felsch style are preferentially filled (subject to the value of fill). If the argument is 1, they are filled immediately, and if it is 2, the consequent deduction is also made immediately (of course, these are also put on the deduction stack). If the argument is 3, then the gaps of length one are noted in the preferred definition queue.

Provided such a gap survives (and no coincidence occurs, which causes the queue to be discarded) the next coset number will be defined to fill the oldest gap of length one. The default value is either 0 or 3, depending on the strategy selected (see Chapter Strategy Options for ACE). If you want to know more details, read the code.

psize:=val

Size of preferred definition queue; val must be 0 or 2ⁿ, for some integer n > 0. (Shortest abbreviation: psiz.)

The preferred definition queue is implemented as a ring, dropping earliest entries. An argument of 0 selects the default size of 256. Each queue slot takes two words (i.e., 8 bytes), and the queue can store up to 2ⁿ−1 entries.

4.15 ACE Parameter Options for R Style Definitions

row:=val

Set the ``row filling'' option; val is either 0 or 1.

By default, ``row filling'' is on (i.e. true or 1). To turn it off set row to false or 0 (both are translated to 0 when passed to the ACE binary). When making HLT style (i.e. R style; see Section Enumeration Style) definitions, rows of the coset table are scanned for holes after its coset number has been applied to all relators, and definitions are made to fill any holes encountered. This will, in particular, guarantee fulfilment of the condition of Mendelsohn's Theorem. Failure to do so can cause even simple enumerations to overflow.

lookahead:=val

Lookahead; val should be in the integer range 0 to 4. (Shortest abbreviation: look.)

Although HLT style strategies are fast, they are local, in the sense that the implications of any definitions/deductions made while applying coset numbers may not become apparent until much later. One way to alleviate this problem is to perform lookaheads occasionally; that is, to test the information in the table, looking for deductions or concidences. ACE can perform a lookahead when the table overflows, before the compaction routine is called. Lookahead can be done using the entire table or only that part of the table above the current coset number, and it can be done R style (scanning coset numbers from the beginning of relators) or C style (testing all definitions in all essentially different positions).

The following are the effects of the possible values of lookahead:

• 0 disables lookahead;
• 1 does a partial table lookahead, R style;
• 2 does a whole table lookahead, C style;
• 3 does a whole table lookahead, R style; and
• 4 does a partial table lookahead, C style.

The default is 1 if the hlt strategy is used and 0 otherwise; see Chapter Strategy Options for ACE.

Section Enumeration Style describes the various enumeration styles, and, in particular, R style and C style.

4.16 ACE Parameter Options for Deduction Handling

dmode:=val

Deduction mode; val should be in the integer range 0 to 4. (Shortest abbreviation: dmod.)

A completed table is only valid if every table entry has been tested in all essentially different positions in all relators. This testing can either be done directly (felsch strategy; see option felsch) or via relator scanning (hlt strategy; see option hlt). If it is done directly, then more than one deduction (i.e., table entry) can be waiting to be processed at any one time. So the untested deductions are stored in a stack. Normally this stack is fairly small but, during a collapse, it can become very large.

This command allows the user to specify how deductions should be handled. The value val has the following interpretations:

• 0: discard deductions if there is no stack space left;

• 1: as for 0, but purge any redundant coset numbers on the top of the stack at every coincidence;

• 2: as for 0, but purge all redundant coset numbers from the stack at every coincidence;

• 3: discard the entire stack if it overflows; and

• 4: if the stack overflows, double the stack size and purge all redundant coset numbers from the stack.

The default deduction mode is either 0 or 4, depending on the strategy selected (see Chapter Strategy Options for ACE), and it is recommended that you stay with the default. If you want to know more details, read the well-commented C code.

Notes: If deductions are discarded for any reason, then a final relator check phase will be run automatically at the end of the enumeration, if necessary, to check the result.

dsize:=val

Deduction stack size; val should be a non-negative integer. (Shortest abbreviation: dsiz.)

Sets the size of the (initial) allocation for the deduction stack. The size is in terms of the number of deductions, with one deduction taking two words (i.e., 8 bytes). The default size, of 1000, can be selected by a value of 0. See the dmode entry for a (brief) discussion of deduction handling.

4.17 Technical ACE Parameter Options

The following options do not affect how the coset enumeration is done, but how it uses the computer's resources. They might thus affect the runtime as well as the range of problems that can be tackled on a given machine.

workspace:=val

Workspace size in words (default 10⁸); val should be an expression that evaluates to a positive integer, or a string of digits ending in a k, M or G representing a multiplication factor of 10³, 10⁶ or 10⁹, respectively e.g. both workspace := 2 * 10^6 and workspace := "2M" specify a workspace of 2×10⁶ words. Actually, if the value of workspace is entered as a string, each of k, M or G will be accepted in either upper or lower case. (Shortest abbreviation: wo.)

By default, ACE has a physical table size of 10⁸ words (i.e., 4 ×10⁸ bytes in the default 32-bit environment). The number of coset numbers in the table is the table size divided by the number of columns. Although the number of coset numbers is limited to 2³¹−1 (if the C int type is 32 bits), the table size can exceed the 4GByte 32-bit limit if a suitable machine is used.

time:=val

Maximum execution time in seconds; val must be an integer greater than or equal to −1. (Shortest abbreviation: ti.)

The time command puts a time limit (in seconds) on the length of a run. The default is −1 which is no time limit. If the argument is ≥ 0 then the total elapsed time for this call is checked at the end of each pass through the enumerator's main loop, and if it's more than the limit the run is stopped and the current table returned.

Note that a limit of 0 performs exactly one pass through the main loop, since 0 ≥ 0.

The time limit is approximate, in the sense that the enumerator may run for a longer, but never a shorter, time. So, if there is, e.g., a big collapse (so that the time round the loop becomes very long), then the run may run over the limit by a large amount.

Notes: The time limit is CPU-time, not wall-time. As in all timing under UNIX, the clock's granularity (usually 10 milliseconds) and the system load can affect the timing; so the number of main loop iterations in a given time may vary.

loop:=val

Loop limit; val should be a non-negative integer.

The core enumerator is organised as a state machine, with each step performing an ``action'' (i.e., lookahead, compaction) or a block of actions (i.e., |ct| coset number definitions, |rt| coset number applications). The number of passes through the main loop (i.e., steps) is counted, and the enumerator can make an early return when this count hits the value of loop. A value of 0, the default, turns this feature off.

Guru Notes: You can do lots of really neat things using this feature, but you need some understanding of the internals of ACE to get real benefit from it.

path

Turns on path compression.

To correctly process multiple concidences, a union-find must be performed. If both path compression and weighted union are used, then this can be done in essentially linear time (see, e.g., CLR90). Weighted union alone, in the worst-case, is worse than linear, but is subquadratic. In practice, path compression is expensive, since it involves many coset table accesses. So, by default, path compression is turned off; it can be turned on by path. It has no effect on the result, but may affect the running time and the internal statistics.

Guru Notes: The whole question of the best way to handle large coincidence forests is problematic. Formally, ACE does not do a weighted union, since it is constrained to replace the higher-numbered of a coincident pair. In practice, this seems to amount to much the same thing! Turning path compression on cuts down the amount of data movement during coincidence processing at the expense of having to trace the paths and compress them. In general, it does not seem to be worthwhile.

compaction:=val

Percentage of dead coset numbers to trigger compaction; val should be an integer (percentage) in the integer range 0 to 100. (Shortest abbreviation: com.)

The option compaction sets the percentage of dead coset numbers needed to trigger compaction of the coset table, during an enumeration. A dead coset (number) is a coset number found to be coincident with a smaller coset number. The default is 10 or 100, depending on the strategy used (see Chapter Strategy Options for ACE).

Compaction recovers the space allocated to coset numbers which are flagged as dead. It results in a table where all the active coset numbers are numbered contiguously from 1, and with the remainder of the table available for new coset numbers.

The coset table is compacted when a definition of a coset number is required, there is no space for a new coset number available, and provided that the given percentage of the coset table contains dead coset numbers. For example, if compaction = 20 then compaction will occur only if 20% or more of the coset numbers in the table are dead. An argument of 100 means that compaction is never performed, while an argument of 0 means always compact, no matter how few dead coset numbers there are (provided there is at least one, of course).

Compaction may be performed multiple times during an enumeration, and the table that results from an enumeration may or may not be compact, depending on whether or not there have been any coincidences since the last compaction (or from the start of the enumeration, if there have been no compactions).

Notes: In some strategies (e.g., hlt; see option hlt) a lookahead phase may be run before compaction is attempted. In other strategies (e.g., sims := 3; see option sims) compaction may be performed while there are outstanding deductions; since deductions are discarded during compaction, a final lookahead phase will (automatically) be performed.

Compacting a table ``destroys'' information and history, in the sense that the coincidence list is deleted, and the table entries for any dead coset numbers are deleted.

max:=val

Sets the maximum coset number that can be defined; val should be 0 or an integer greater than or equal to 2.

By default (which is the case max=0), all of the workspace is used, if necessary, in building the coset table. So the table size (in terms of the number of rows) is an upper bound on how many coset numbers can be alive at any one time. The max option allows a limit to be placed on how much physical table space is made available to the enumerator. Enough space for at least two coset numbers (i.e., the subgroup and one other) must be made available.

Notes: If the easy strategy (see option easy) is selected, so that compaction (see option compaction) is off (i.e. set to 100) and lookahead (see option lookahead) is off (i.e. set to 0), and max is set to a positive integer, then coset numbers are not reused, and hence max bounds the total number totcosets (see Section Coset Statistics Terminology) of coset numbers defined during an enumeration.

On the other hand, if one (or both) of compaction or lookahead is not off, then some reuse of coset numbers may occur, so that, for the case where max is a positive integer, the value of totcosets may be greater than max.

However, whenever max is set to a positive integer, both activecosets (the number of alive coset numbers at the end of an enumeration) and maxcosets (the maximum number of alive coset numbers at any point of an enumeration) are bounded by max. See Section Coset Statistics Terminology, for a discussion of the terminology: activecosets and maxcosets.

hole:=val

Maximum percentage of holes allowed during an enumeration; val should be an integer in the range −1 to 100. (Shortest abbreviation: ho.)

This is an experimental feature which allows an enumeration to be terminated when the percentage of holes in the table exceeds a given value. In practice, calculating this is very expensive, and it tends to remain constant or decrease throughout an enumeration. So the feature doesn't seem very useful. The default value of −1 turns this feature off. If you want more details, read the source code.

4.18 ACE Parameter Options controlling ACE Output

messages:=val

monitor:=val

Sets the verbosity of output from ACE; val should be an integer. (Shortest abbreviation of messages is mess, and shortest abbreviation of monitor is mon.)

By default, val = 0, for which ACE prints out only a single line of information, giving the result of each enumeration. If val is non-zero then the presentation and the parameters are echoed at the start of the run, and messages on the enumeration's status as it progresses are also printed out. The absolute value of val sets the frequency of the progress messages, with a negative sign turning hole monitoring on. Note that, hole monitoring is expensive, so don't turn it on unless you really need it.

Note that, ordinarily, one will not see these messages: non-interactively, these messages are directed to file ACEData.outfile (or filename, if option aceoutfile := filename, or ao := filename, is used), and interactively these messages are simply not displayed. However, one can change this situation both interactively and non-interactively by setting the InfoLevel of InfoACE to 3 via

gap> SetInfoACELevel(3);

Then ACE's messages are displayed prepended with ``#I ''. Please refer to Appendix The Meanings of ACE's output messages, where the meanings of ACE's output messages are fully discussed.

4.19 ACE Parameter Options that give Names to the Group and Subgroup

These options may be safely ignored; they only give names to the group or subgroup within the ACE output, and have no effect on the enumeration itself.

enumeration:=string

Sets the Group Name to string; string, must of course be a string. (Shortest abbreviation: enum.)

The ACE binary has a two-word synonym for this option: Group Name and this is how it is identified in the ``Run Parameters'' block of the ACE output when messages has a non-zero value. The default Group Name is "G".

subgroup:=string

Sets the Subgroup Name to string; string must of course be a string. (Shortest abbreviation: subg.)

The default Subgroup Name is "H".

4.20 Options for redirection of ACE Output

ao:=filename

aceoutfile:=filename

Redirects (alters) output to filename; filename should be a string.

Non-interactively, output from ACE is normally directed to a temporary file whose full path is stored in ACEData.outfile, which is parsed to produce a coset table or a list of statistics. This option causes ACE's output to be directed to filename instead, presumably because the user wishes to see (and keep) data output by the ACE binary, other than the coset table output from ACECosetTableFromGensAndRels or the statistics output by ACEStats. Please refer to Appendix The Meanings of ACE's output messages, where we discuss the meaning of the additional data to be found in the ACE binary's output. The option aceoutfile is a GAP-introduced synonym for ao, that is translated to ao before submission to the ACE binary. Do not use option aceoutfile when running the standalone directly. Happily, ao can also be regarded as mnemonical for aceoutfile.

4.21 Other Options

ACE has a number of other options, but the GAP user will not ordinarily need them, since, in most cases, alternative interactive functions exist. These remaining options have been relegated to Appendix Other ACE Options. The options listed there may be used both interactively and non-interactively, but many are probably best used directly via the ACE standalone.

[Up] [Previous] [Next] [Index]