Constructing permutation representations for large matrix groups

ABSTRACT

New techniques, both theoretical and practical, are presented for constructing a permutation representation for a matrix group. We assume that the resulting permutation degree, n, can be 10,000,000 and larger. The key idea is to build the new permutation representation using the conjugation action on a conjugacy class of subgroups of prime order. A unique signature for each group element corresponding to the conjugacy class is used in order to avoid matrix multiplication. The requirement of at least n matrix multiplications would otherwise have made the computation hopelessly impractical. Additional software optimizations are described, which reduce the CPU time by at least an additional factor of 10. Further, a special data structure is designed that serves both as a search tree and as a hash array, while requiring space of only 1.6n log2 n bits.The technique has been implemented and tested on the sporadic simple group Ly, discovered by Lyons [9], in both a sequential (SPARCserver 670MP) and parallel SIMD (MasPar MP-1) version. Starting with a generating set for Ly as a subgroup of GL(111,5) [5], a set of generating permutations for Ly acting on 9, 606, 125 points is constructed as well as a base for this permutation representation. The sequential version required four days of CPU time to construct a data structure which can be used to compute the permutation image of an arbitrary matrix. The parallel version did so in 12 hours. Work is in progress on a faster parallel implementation.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: V.L. Arlazarov, E.A. Dinic, M.A. Kronrod and I.A. Faradzev, "On EconomicM Construction of the Transitive Closure of a Directed Graph", Dokl. Nauk SSSR 194, pp. 487-488. English translation in Soviet Math. Dokl. 11:5, pp. 1209-1210.
• 3: László Babai, Local expansion of vertex-transitive graphs and random generation in finite groups, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.164-174, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103440]
• 4: L. Babai and R. BeMs, "Las Vegas Algorithms for Matrix Groups", to appear.
• 5: H. Conway, R. T. Curtis, S. P. Norton, R. A. Parker, R. A. Wilson: Atlas of Finite Groups, Clarendon Press, Oxford (1985).
• 6: C. Leedham-Green et al., Lecture at the MAGMA Conference, London, England, July, 1993.
• 7: S. Linton, "The Art and Science of Computing in Large Groups", to appear in Proceedings of the Computational Algebra and Number Theory conference (CANT), Sydney, November, 1992.
• 8: E. M. Luks, "Computing in Solvable Matrix Groups", Proc. 33rd IEEE FOCS (1992), pp. 111-120.
• 9: R. Lyons, "Evidence for a New Finite Simple Group", Journal of Algebra, 20 (1972), pp. 540-569.
• 10: G. Michler, lecture at Northeastern University, October, 1993.
• 11: R. Parker, "The computer calculation of modular characters. (The Meat-Axe)", in M. Atkinson (ed.), Computational Group Theory, Academic Press, London, pp. 267-274, 1984.
• 12: C. C. Sims, "The Existence and Uniqueness of Lyons' Group", Proc. of the Gainseville Conference (1972), pp. 138-141.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Arrays

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Permutations and combinations

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

General Terms:
Algorithms, Design, Performance