GAP Responding Time

Question

I am running GAP 4.6.5 on my six-year-old computer and sometimes it takes like forever for GAP to respond to my simple commands. An easy example is as follows:

f:=FreeGroup("x","y");x:=f.1;y:=f.2;
n:=[Comm(Comm(x,y),x)];
g:=f/n;
Order(Comm(Comm(g.1,g.2),g.1));

It should be obvious that the order of $[[g.1,g.2],g.1]$ is $1$. However, when I run the last command in GAP, it takes like forever for GAP to respond. From the Windows Task Manager I know that GAP is still running very hard but it just does not give any result. I just do not understand why GAP cannot solve such a trivial problem immediately.

A related question is: After hitting "Enter" how can we roughly know how long it would take for GAP to respond? From my experience sometimes it could be a few minutes and sometimes it does not respond after several hours and I choose to terminate it. If I know it would respond in say six hours I probably can wait; but what if it takes dozens or hundreds of hours, or even longer?

Answer 1

This question is actually two-fold. Let me try to shed some light on both parts. I will start from the second one - if one would know how to find out what GAP was doing during the long calculation, that probably would lead you to looking at the relevant manual chapters and finding there pointers to further related functionality.

In many situations there is no way to "guesstimate" how long the calculation will be. If you have a loop over some range, you may print the number of the current iteration, but if the calculation is irregular, the remaining iterations may take much longer than observed. If you have an exponential algorithm, then you may try it for small arguments and find out where it becomes practically unfeasible. However, the example from the question does not fit into the above.

What you could do, however, is (a) to use the Info mechanism and (b) to interrupt the calculation to explore the break loop. Sometimes you may need to interrupt it several times, in a hope to see different parts of the code which GAP is visiting. To interrupt the calculation, you have to press Ctrl-C. For example, in the same settings as above, I have

gap> f:=FreeGroup("x","y");x:=f.1;y:=f.2;
<free group on the generators [ x, y ]>
x
y
gap> n:=[Comm(Comm(x,y),x)];
[ y^-1*x^-1*y*x^-1*y^-1*x*y*x ]
gap> g:=f/n;
<fp group of size infinity on the generators [ x, y ]>
gap> g.1;
x

Now I am asking what's the order of g.1 and then pressing Ctrl-C after some time:

gap> Order(g.1);
^CError, user interrupt in
  b := ReduceLetterRepWordsRewSys( kbrws!.tzrules, u[2] ); called from 
AddRuleReduced( kbrws, [ a, c ] ); called from
KBOverlaps( i[1], i[2], kbrws, p ) called from
KB_REW.MakeKnuthBendixRewritingSystemConfluent( rws ); called from
MakeKnuthBendixRewritingSystemConfluent( kbrws ); called from
MakeConfluent( kbrws ); called from
...  at line 5 of *stdin*
you can 'return;'
brk> quit;

This a break loop, where I can inspect values of variables, enter return; to continue (and press Ctrl-C later again, if I wish) or enter quit; to abandon the calculation and return to the main prompt.

From the backtrace I can deduce that GAP actually spends its time in MakeKnuthBendixRewritingSystemConfluent. Same happens if you will ask about Order(Comm(Comm(g.1,g.2),g.1)) - before making any further steps, it first tries to make the system confluent. Looking at Info classes (enter Info and hit Tab twice) you may discover that there is an Infoclass InfoKnuthBendix. I do not know what is its maximal setting, but I suspect 10 will be more than enough. Now I have:

gap> SetInfoLevel(InfoKnuthBendix,10);
gap> Order(g.1);
#I  MakeKnuthBendixRewritingSystemConfluent called
#I  51 rules, 2276 pairs
#I  102 rules, 9394 pairs
#I  145 rules, 19488 pairs
#I  178 rules, 29780 pairs
#I  205 rules, 39904 pairs
...
#I  1256 rules, 1569302 pairs
#I  1250 rules, 1554214 pairs
#I  1255 rules, 1566680 pairs
#I  1259 rules, 1576686 pairs
...
...

and then I decide to terminate the calculation, since I know that the kbmag package by DerekHolt may have better chances to help here. Indeed, it is capable of telling that the commutator in question is equal to the identity element of a group:

gap> LoadPackage("kbmag");
-----------------------------------------------------------------
Loading  kbmag 1.5 (Knuth-Bendix on Monoids and Automatic Groups)
by Derek Holt (http://www.warwick.ac.uk/~mareg).
Homepage: http://www.warwick.ac.uk/~mareg/kbmag
-----------------------------------------------------------------
true
gap> rws:=KBMAGRewritingSystem(g);
rec(
           isRWS := true,
          silent := true,
  generatorOrder := [_g1,_g2,_g3,_g4],
        inverses := [_g2,_g1,_g4,_g3],
        ordering := "shortlex",
       equations := [
         [_g4*_g2*_g3*_g2,_g2*_g4*_g2*_g3]
       ]
)
gap> Rules(rws);
[ [ _g4*_g2*_g3*_g2, _g2*_g4*_g2*_g3 ] ]
gap> KnuthBendix(rws);
false
gap> z:=Comm(Comm(f.1,f.2),f.1);
y^-1*x^-1*y*x^-1*y^-1*x*y*x
gap> ReducedForm(rws,z);
#WARNING: system is not confluent, so reductions may not be to normal form.
<identity ...>

The call to KnuthBendix(rws) also takes a while, but then it finally terminates and returns false since the rewriting system is not confluent - please see kbmag's documentation regarding the meaning of that in more details. However, reductions may be possible modulo the warning above. Note that z must be a word in terms of generators of the initial free group f and not of g.

Thus, as you see, GAP is capable of dealing with infinite groups, but it may be not so straightforward. You may find it interesting to see at Max Neunhoeffers' lectures from LMS/EPSRC Short Course "Computational Group Theory". His slides also contain links to files with GAP examples. Hope that will be helpful!