Memory-based and disk-based algorithms for very high degree permutation groups

ABSTRACT

Group membership is a fundamental algorithm, upon which most other algorithms of computational group theory depend. Until now, group membership for permutation groups has been limited to ten million points or less. We extend the applicability of group membership algorithms to permutation groups acting on more than 100,000,000 points. As an example, we experimentally construct a group membership data structure for Thompson's group, acting on 143,127,000 points, in 36 minutes. More significantly, we require approximately 10 GB of RAM for the computation --- even though a single permutation of Thompson's group already requires half a gigabyte of storage.In addition, we propose a disk-based group membership algorithm with the promise of extending group membership to well over one billion (1,000,000,000) points. Such a disk-based algorithm has formerly been impossible, due in part to the lack of a practical disk-based algorithm for multiplying and taking inverses of such large permutations. Random access to disk is prohibitively expensive. We demonstrate the first practical disk-based implementation of the basic permutation operations. We also propose a disk-based architecture for group membership data structures.

REFERENCES

• 1: 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]
• 2: László Babai , Gene Cooperman , Larry Finkelstein , Eugene Luks , Ákos Seress, Fast Monte Carlo algorithms for permutation groups, Journal of Computer and System Sciences, v.50 n.2, p.296-308, April 1995
• 3: László Babai , Gene Cooperman , Larry Finkelstein , Ákos Seress, Nearly linear time algorithms for permutation groups with a small base, Proceedings of the 1991 international symposium on Symbolic and algebraic computation, p.200-209, July 15-17, 1991, Bonn, West Germany [doi>10.1145/120694.120724]
• 4: László Babai , Eugene M. Luks , Ákos Seress, Fast Management of Permutation Groups I, SIAM Journal on Computing, v.26 n.5, p.1310-1342, Oct. 1997 [doi>10.1137/S0097539794229417]
• 5: Wieb Bosma , John Cannon , Catherine Playoust, The MAGMA algebra system I: the user language, Journal of Symbolic Computation, v.24 n.3-4, p.235-265, Sept./Oct. 1997 [doi>10.1006/jsco.1996.0125]
• 6: G. Butler and J. J. Cannon. Computing in permutation and matrix groups I: Normal closure, commutator subgroups, series. Math. Comp., 39:663--670, 1982.
• 7: F. Celler, C. R. Leedham-Green, S. H. Murray, A. C. Niemeyer, and E. O'Brien. Generating random elements of a finite group. Comm. Algebra, 23:4931--4948, 1995.
• 8: G. Cooperman. Towards a practical, theoretically sound algorithm for random generation in finite groups. arXiv:math.PR/0205203, http://arxiv.org/abs/math.PR/0205203.
• 9: 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]
• 10: G. Cooperman and L. Finkelstein. Randomized algorithms for permutation groups. Centrum Wissenschaft Institut Quarterly (CWI), pages 107--125, June 1992.
• 11: G. Cooperman and L. Finkelstein. Combinatorial tools for computational group theory. In Groups and Computation, volume 11 of Amer. Math. Soc. DIMACS Series, pages 53--86. (DIMACS, 1991), 1993.
• 12: Gene Cooperman , Larry Finkelstein, A random base change algorithm for permutation groups, Journal of Symbolic Computation, v.17 n.6, p.513-528, June 1994 [doi>10.1006/jsco.1994.1032]
• 13: G. Cooperman , L. Finkelstein , N. Sarawagi, A random base change algorithm for permutation groups, Proceedings of the international symposium on Symbolic and algebraic computation, p.161-168, August 20-24, 1990, Tokyo, Japan [doi>10.1145/96877.96918]
• 14: Gene Cooperman , Larry Finkelstein , Michael Tselman , Bryant York, Constructing permutation representations for matrix groups, Journal of Symbolic Computation, v.24 n.3-4, p.471-488, Sept./Oct. 1997 [doi>10.1006/jsco.1997.0146]
• 15: Gene Cooperman , Larry Finkelstein , Bryant York , Michael Tselman, Constructing permutation representations for large matrix groups, Proceedings of the international symposium on Symbolic and algebraic computation, p.134-138, July 20-22, 1994, Oxford, United Kingdom [doi>10.1145/190347.190384]
• 16: Gene Cooperman , Victor Grinberg, Scalable parallel coset enumeration: bulk definition and the memory wall, Journal of Symbolic Computation, v.33 n.5, p.563-585, May 2002 [doi>10.1006/jsco.2002.0523]
• 17: G. Cooperman and G. Havas. Practical parallel coset enumeration. In Workshop on High Performance Computing and Gigabit Local Area Networks, volume 226 of Lecture Notes in Control and Information Sciences, pages 15--27, 1997.
• 18: G. Cooperman, G. Hiss, K. Lux, and J. Müller. The Brauer tree of the principal $19$-block of the sporadic simple thompson group. J. Experimental Math., 6:293--300, 1997.
• 19: G. Cooperman, W. Lempken, G. Michler, and M. Weller. A new existence proof of Janko's simple group J4. In Computational Methods for Representations of Groups and Algebras, volume 173 of Progress in Mathematics, pages 161--175, 1999.
• 20: Gene Cooperman , Xiaoqin Ma, Overcoming the memory wall in symbolic algebra: a faster permutation multiplication, ACM SIGSAM Bulletin, v.36 n.4, December 2002 [doi>10.1145/641239.641241]
• 21: Gene Cooperman , Michael Tselman, New sequential and parallel algorithms for generating high dimension Hecke algebras using the condensation technique, Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.155-160, July 24-26, 1996, Zurich, Switzerland [doi>10.1145/236869.236927]
• 22: The GAP Group. GAP --- Groups, Algorithms, and Programming, Version 4.3, 2002. http://www.gap-system.org.
• 23: H. Gollan. A new existence proof for Ly, the sporadic simple group of R. Lyons. Preprint 30, 1995.
• 24: H. Gollan. A contribution to the revision project of the sporadic groups: Lyons' simple group Ly. Vorlesungen aus dem FB Mathematik, 26, 1997.
• 25: Holger W. Gollan, A new existence proof for Ly, the sporadic simple group of R. Lyons, Journal of Symbolic Computation, v.31 n.1-2, p.203-209, Jan./Feb. 2001 [doi>10.1006/jsco.2000.1010]
• 26: H. Gollan and G. Havas. On Sims' presentation for Lyons' simple group. In Computational Methods for Representations of Groups and Algebras, volume 173 of Progress in Mathematics, pages 235--240, 1999.
• 27: G. Havas and C. Sims. A presentation for the Lyons simple group. In Computational Methods for Representations of Groups and Algebras, volume 173 of Progress in Mathematics, pages 241--249, 1999.
• 28: G. Havas, L. Soicher, and R. Wilson. A presentation for the Thompson sporadic simple group. In Groups and Computation III, pages 193--200, New York, 2001. (Ohio, 1999), de Gruyter.
• 29: W. M. Kantor. Sylow's theorem in polynomial time. J. Comp. Syst. Sci., 30:359--394, 1985.
• 30: C. Leedham-Green. The computational matrix group project. In Groups and Computation rm III, pages 229--248, New York, 2001. (Ohio, 1999), de Gruyter.
• 31: C. Leedham-Green, E. O'Brien, and C. Praeger. Recognising matrix groups. In J. Grabmeier, E. Kaltofen, and V. Weispfenning, editors, Computer Algebra Handbook, pages 474--475, 2003.
• 32: E. M. Luks, Computing the composition factors of a permutation group in polynomial time, Combinatorica, v.7 n.1, p.87-99, Jan. 1987 [doi>10.1007/BF02579204]
• 33: I. Pak, The product replacement algorithm is polynomial, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.476, November 12-14, 2000
• 34: Raghu Ramakrishnan , Johannes Gehrke, Database Management Systems, McGraw-Hill Higher Education, 2000
• 35: 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]
• 36: M. Weller. Construction of large permutation representations for matrix groups. In W. J. E. Krause, editor, High Performance Computing in Science and Engineering '98, pages 430--. Springer, 1999.
• 37: M. Weller. Construction of large permutation representations for matrix groups ii. Applicable Algebra in Engineering, Communication and Computing, 11:463--488, 2001.
• 38: M. Weller. Computer aided existence proof of Thompson's sporadic simple group. manuscript, 2003.
• 39: R. Wilson. Atlas of finite group representations. http://www.mat.bham.ac.uk/atlas.

INDEX TERMS

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

General Terms:
Algorithms, Experimentation

Keywords:
Thompson's group, disk-based methods, group membership, permutation groups, permutation multiplication