×

Nearly linear time algorithms for permutation groups: An interplay between theory and practice. (English) Zbl 0915.20001

This paper contains a nice survey of permutation group algorithms, concentrating on those which are polynomial time but also mentioning some which are not. The focus is on asymptotic analysis but practical implementations are mentioned also. This paper emphasizes “nearly linear time” algorithms, that is, those whose time bound is \(O(n\log^c| G|)\) for a permutation group \(G\) of degree \(n\). (In the important case of small-base groups this time bound is linear except for factors of \(\log n\).) After surveying several existing algorithms, the author presents some new nearly linear time algorithms (building on previous methods), culminating in one for finding the upper central series of a nilpotent group. This new algorithm is deterministic, unlike many other nearly linear time algorithms.

MSC:

20B40 Computational methods (permutation groups) (MSC2010)
68W10 Parallel algorithms in computer science
68W30 Symbolic computation and algebraic computation
68Q25 Analysis of algorithms and problem complexity

Software:

Magma; nauty
PDFBibTeX XMLCite
Full Text: DOI