Large-Base Groups
Ákos Seress · Cambridge University Press eBooks · 2003
The central theme of this book is the design and analysis of nearly linear-time algorithms. Given a permutation group G = 〈 S 〉 ≤ Sym(Ω), with |Ω| = n , such algorithms run in O (| S | n log c | G |) time for some constant c . If, as happens most of the time in practice, log | G | is bounded from above by a polylogarithmic function of n then these algorithms run in time that is nearly linear as a function of the input length | S | n . In most cases, we did not make an effort to minimize the exponent c of log | G | in the running time since achieving the smallest possible exponent c was not the most pressing problem from either the theoretical or practical point of view. However, in families of groups where log | G | or, equivalently, the minimal base size of G is large, the nearly linear-time algorithms do not run as fast as their name indicates; in fact, for certain tasks, the may not be the asymptotically fastest algorithms at all. Another issue is the memory requirement of the algorithms, which again may be unnecessarily high. The purpose of this chapter is to describe algorithms that may be used in the basic handling of large-base groups. The practical limitation is their memory requirement, which is in most cases a quadratic function of n .