This chapter briefly discusses some performance issues with the use of the SmallOverlap package.
Most of the routines implemented require time and space which is quadratic in the presentation lengths, and linear in the element lengths. For a detailed complexity analysis of the algorithms see [Kam07].
We have already remarked that the small overlap equality test method is not automatically installed, since testing whether small overlap methods are applicable inevitably imposes a slight performance overhead when computing with monoids in which they turn out not to be applicable. More precisely, when the equality test method is installed:
Testing the C(4) condition is carried out once per presentation. This takes time quadratic (with very small coefficients) in the presentation length, so is only likely to be noticeable if working with very large presentations, or with extremely large numbers of presentations.
Checking each element to see if the containing fp monoid or semigroup has the C(4) property is carried out once per element. This should be done in constant time (assuming GAP is reasonably efficient in its internal implementation of function calls and attribute tests) but this may still be appreciable if you are carrying out vast numbers of equality tests in the same monoid, and that monoid does not satisfy C(4).
In addition, one could almost certainly construct examples of C(4) monoids where the standard GAP equality test algorithm (reduction to normal form using a confluent rewriting system created by Knuth-Bendix completion) runs even faster than the small overlap algorithm. In practice the latter is so fast that in such a case it is unlikely to matter much which algorithm is used but, once again, performing very large numbers of equality tests in such a monoid could in principle be slower with the small overlap routines.
For most purposes these penalties are negliglible, and since the vast majority of monoids do satisfy C(4), likely to be vastly outweighed by the time saved by using small overlap methods where applicable. Hence, unless you are performing very large numbers of equality tests, and moreover have definite reason to believe that a large proportion of these will be in monoids not satisfying C(4), we strongly recommend that you call PreferSmallOverlapEqualityTest
.
generated by GAPDoc2HTML