Martin Schönert
ABSTRACT
The purpose of this note is to describe a new algorithm for finding blocks of imprimitivity for a permutation group G, operating on a domain Ω.
It runs in O(n log3|G| + ns log|G|) time, where n is the size of Ω and s is the number of generators for G. In many situations it is therefore faster than Atkinson's method, which runs in O(n2s) time.
A base of G is a subset B ⊆ Ω such that only the identity of G fixes B pointwise. We call a family of groups small-base groups if they admit bases of size O(logc n) for some fixed constant c.
If G belongs to a family of small-base groups, our algorithm runs in nearly linear time, namely in O(ns logc′ n). Beals recently gave an algorithm with the same worst case estimate. Our algorithm is simpler to implement and we expect faster practical performance.
- AHU.A.V. Aho, 3.E. Hopcroft, J.D. Ullman: The Design and Analysis of Computer Algorithms, Addison- Wesley, Reading 1974, pp. 189-195. Google Scholar
Digital Library
- Atk.M.D. Atkinson: An algorithm for finding the blocks of a permutation group, Math. Comp. 29 (1975), pp. 911- 913.Google ScholarCross Ref
- BCFS.L. Babai, G. Cooperman, L. Finkelstein,/~. Seress" Nearly linear time Mgorithms for permutation groups with a smM1 base, Proc ISSAC'91 (Internat. Symp. on Symbolic and Algebraic Computation), Bonn 1991, pp. 200-209. Google ScholarDigital Library
- Be.R. Beals: Computing blocks of imprimitivity for smallbase groups in nearly linear time, DIMACS Series in Discrete Mathematics and Computer Science, 11 (1993), pp. 17-26.Google ScholarCross Ref
- BeS.R. Beals,/~. Seress: Structure forest and composition factors for small base groups in nearly linear time, Proc 24th ACM STOC (1992), pp. 116-125. Google ScholarDigital Library
- LS.E. Luks,/~. Seress: Nearly linear time computation of the Fitting subgroup and radical in small-base groups, in preparation.Google Scholar
- Schö.M. SchSnert et al: Groups, Algorithms, and Programming, Version 3, Release 2, RWTH Aachen, 1992.Google Scholar
- SW.A. Seress, I. Weisz: PERM' a program computing strong generating sets, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 11 (1993), pp. 269-276.Google ScholarCross Ref
- Sim.C.C. Sims: Computation with Permutation Groups, in: Proc. Second Syrup. on Symbolic and Algebraic Manipulation, ACM, New York, 1971, pp. 23-28. Google ScholarDigital Library
- Ta.R. E. Tarjan, Depth first search and linear graph algorithms, SIAM J. Comp. 1 (1972), pp. 146-160.Google ScholarCross Ref
- Wi.H. Wielandt: Finite Permutation Groups, Acad. Press, New York 1964.Google Scholar
Index Terms
- Finding blocks of imprimitivity in small-base groups in nearly linear time
Recommendations
Structure forest and composition factors for small base groups in nearly linear time
STOC '92: Proceedings of the twenty-fourth annual ACM symposium on Theory of ComputingA base of a permutation group G is a subset B of the permutation domain such that only the identity of G fixes B pointwise. The permutation representations of important classes of groups, including all finite simple groups other than the alternating ...
Sorting in Linear Time?
We show that a unit-cost RAM with a word length ofwbits can sortnintegers in the range 0 2w 1 inO(nloglogn) time for arbitraryw logn, a significant improvement over the bound ofO(nlogn) achieved by the fusion trees of Fredman and Willard. Provided thatw ...
Super-linear time-space tradeoff lower bounds for randomized computation
FOCS '00: Proceedings of the 41st Annual Symposium on Foundations of Computer ScienceWe prove the first time-space lower bound tradeoffs for randomized computation of decision problems. The bounds hold even in the case that the computation is allowed to have arbitrary probability of error on a small fraction of inputs. Our techniques ...
Comments