A random base change algorithm for permutation groups

ABSTRACT

A new random base change algorithm is presented for a permutation group G acting on n points whose worst case asymptotic running time is better for groups with a small to moderate size base than any known deterministic algorithm. To achieve this time bound, the algorithm requires a random generator Rand(G) producing a random element of G with the uniform distribution and so that each call to Rand(G) takes time &Ogr;(log(|G|)n). The random base change algorithm has probability 1 -- 1/|G|2 of completing in time &Ogr;(log2(|G|)n) and outputting a data structure for representing the point stabilizer sequence relative to the new ordering which requires &Ogr;(log(|G|)n) space and which can be used to test group membership in time &Ogr;,(log(|G|)n). The time to build a data structure for computing a Rand(G) with the above properties from a strong generating set for G is dominated by the time to construct the strong generating set from the original set of generators.

REFERENCES

• 1: L. Babai, "Monte-Carlo Algorithms in Graph Isomorphism Testing", Tech. Rep. 79-10, Dep. Math. et Stat., Univ. de Montreal, 1979.
• 2: C. A. Brown , L. Finkelstein , P. W. Purdom, Jr., A new base change algorithm for permutation groups, SIAM Journal on Computing, v.18 n.5, p.1037-1047, Oct. 1989 [doi>10.1137/0218070]
• 3: Cynthia A. Brown , Larry Finkelstein , Paul Walton Purdom, Jr., Backtrack Searching in the Presence of Symmetry, Proceedings of the 6th International Conference, on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.99-110, July 04-08, 1988
• 4: G. Butler and J.J. Cannon, "Computing in Permutation and M~trix Groups I: Normal Closure, Commutator Subgroups, Series" Math. Comp. 39 (1982), pp. 663-670.
• 5: G. Butler and Lam, "Isomorphism Testing of Combinatorial Objects", Y. of Symbolic Computation, (1985).
• 6: J.J. Cannon, "An Introduction to the Group Theory Language, Cayley", in Computational Group Theory, edited by M.D. Atkinson, Academic Press, 1984, pp. 145-184.
• 7: It. Chernoff, "A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the Sum of Observations'', Annals of Math. Statistics 23, (1952).
• 8: Gene Cooperman , Larry Finkelstein, New methods for using Cayley graphs in interconnection networks, Discrete Applied Mathematics, 37-38, p.95-118, July 15, 1992 [doi>10.1016/0166-218X(92)90127-V]
• 9: Gene Cooperman , Larry Finkelstein, A strong generating test and short presentations for permutation groups, Journal of Symbolic Computation, v.12 n.4-5, p.475-497, Oct./Nov. 1991 [doi>10.1016/S0747-7171(08)80099-5]
• 10: G. Cooperman , L. Finkelstein , E. Luks, Reduction of group constructions to point stabilizers, Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation, p.351-356, July 17-19, 1989, Portland, Oregon, United States [doi>10.1145/74540.74581]
• 11: G. Cooperman , L. Finkelstein , P. W. Purdom, Jr., Fast group membership using a strong generating test for permutation groups, Proceedings of the third conference on Computers and mathematics, p.27-36, May 1989, Boston, Massachusetts, United States
• 12: Mark Jerrum, A compact representation for permutation groups, Journal of Algorithms, v.7 n.1, p.60-78, March 1986 [doi>10.1016/0196-6774(86)90038-6]
• 13: D.E. Knuth, "Notes on Efficient Representation of Permutation Groups" (1981), unpublished manuscript.
• 14: J. Leon, "Computing Automorphism Groups of Combinatorial Objects", in Computational Group Theory, edited by M. D. Atkinson, Academic Press (1984), pp. 321-337.
• 15: A. Niemeyer, W. Nickel, and M. SchSnert, GAP: Getting started and Reference manual, Lehrstuhl D fiir Mathematik, RWTH Aachen, Germany.
• 16: Charles C. Sims, Computation with permutation groups, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.23-28, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806264]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms