Article

A parallel architecture for disk-based computing over the Baby Monster and other large finite simple groups

Authors:

Gene CoopermanAuthors Info & Claims

ISSAC '06: Proceedings of the 2006 international symposium on Symbolic and algebraic computation

Pages 298 - 305

https://doi.org/10.1145/1145768.1145817

Published: 09 July 2006 Publication History

Abstract

We outline a distributed, disk-based technique for computing over very large matrix groups. This technique is used to compute a permutation representation for the Baby Monster, a sporadic simple group that acts on 13,571,955,000 points. Its group order is approximately 4 × 10³³. This is a landmark because it is 100 times larger than any previous construction of a permutation representation. By using the computed on-disk data structures, computation over the Baby Monster is now feasible using the distributed disks of a cluster. Our work allows researchers to use either a matrix, a permutation, or a word representation for computing over the Baby Monster where previously only a matrix representation was available. The methodology is demonstrated by using as a signature the image of a vector that is stabilized by the maximal subgroup. The technique extends to finite simple groups and to other groups, through other signatures.

References

[1]

L. Babai, G. Cooperman, L. Finkelstein, E. M. Luks, and A. Seress. Fast Monte Carlo algorithms for permutation groups. J. Comp. Syst. Sci., 50:296--308, 1995.

Digital Library

[2]

L. Babai, G. Cooperman, L. Finkelstein, and A. Seress. Nearly linear time algorithms for permutation groups with a small base. In Proc. of International Symposium on Symbolic and Algebraic Computation ISSAC '91, pages 200--209. (Bonn), ACM Press, 1991.

Digital Library

[3]

L. Babai, E. M. Luks, and A. Seress. Fast management of permutation groups I. SIAM J. Computing, 26:1310--1342, 1997.

Digital Library

[4]

L. Babai and A. Shalev. Recognizing simplicity of black-box groups and the frequency of p-singular elements in affine groups. In Groups and Computation III, Ohio State Univ. Math. Res. Inst. Publ., Berlin, 2000. (Ohio, 1999), de Gruyter.

[5]

W. Bosma, J. Cannon, and C. Playoust. The magma algebra system i: The user language. J. Symbolic Comput., 24:235--265, 1997.

Digital Library

[6]

G. Butler. The Schreier algorithm for matrix groups. In SYMSAC '76, Proc. ACM Sympos. symbolic and algebraic computation, pages 167--170, New York, 1976. (New York, 1976), Association for Computing Machinery.

[7]

G. Butler and J. J. Cannon. Computing in permutation and matrix groups I: Normal closure, commutator subgroups, series. Math. Comp., 39:663--670, 1982.

[8]

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.

[9]

Cooperman, Finkelstein, and Sarawagi. Applications of cayley graphs. In AAECC: Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, International Conference. LNCS, Springer-Verlag, 1990.

Digital Library

[10]

G. Cooperman. Top-c: A task-oriented parallel c interface. In 5th International Symposium on High Performance Distributed Computing (HPDC-5), pages 141--150. IEEE Press, 1996. software at http://www.ccs.neu.edu/home/gene/topc.html.

Digital Library

[11]

G. Cooperman and L. Finkelstein. Randomized algorithms for permutation groups. Centrum Wissenschaft Institut Quarterly (CWI), pages 107--125, June 1992.

[12]

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.

[13]

G. Cooperman and L. Finkelstein. A random base change algorithm for permutation groups. J. Symbolic Comput., 17:513--528, 1994.

Digital Library

[14]

G. Cooperman, L. Finkelstein, and N. Sarawagi. A random base change algorithm for permutation groups. In Proc. of International Symposium on Symbolic and Algebraic Computation ISSAC '90, pages 161--168, Tokyo, Japan, 1990.

Digital Library

[15]

G. Cooperman, L. Finkelstein, M. Tselman, and B. York. Constructing permutation representations for matrix groups. J. Symbolic Comput., 1997.

Digital Library

[16]

G. Cooperman, L. Finkelstein, B. York, and M. Tselman. Constructing permutation representations for large matrix groups. In Proceedings of International Symposium on Symbolic and Algebraic Computation ISSAC '94, pages 134--138, New York, 1994. (Oxford), ACM Press.

Digital Library

[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]

G. Cooperman and E. Robinson. Memory-based and disk-based algorithms for very high degree permutation groups. In Proc. of International Symposium on Symbolic and Algebraic Computation (ISSAC '03), pages 66--73. ACM Press, 2004.

Digital Library

[21]

G. Cooperman and M. Tselman. New sequential and parallel algorithms for generating high dimension Hecke algebras using the condensation technique. In Proc. of International Symposium on Symbolic and Algebraic Computation (ISSAC '96), pages 155--160. ACM Press, 1996.

Digital Library

[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 new existence proof for Ly, the sporadic simple group of R. Lyons. J. Symbolic Comput., 31:203--209, 2001.

Digital Library

[25]

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.

[26]

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.

[27]

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.

[28]

P. E. Holmes and R. A. Wilson. A new computer construction of the Monster using 2-local subgroups. J. London Math. Soc., 67:349--364, 2003.

[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 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]

S. A. Linton, R. A. Parker, P. G. Walsh, and R. A. Wilson. Computer construction of the Monster. J. Group Theory, 1:307--337, 1998.

[33]

F. Lübeck and M. Neunhöffer. Enumerating large orbits and direct condensation. Experiment. Math, 10:197--206, 2001.

[34]

E. M. Luks. Computing the composition factors of a permutation group in polynomial time. Combinatorica, 7:87--99, 1987.

Digital Library

[35]

S. H. Murray and E. O'Brien. Selecting base points for the Schreier-Sims algorithm for matrix groups. J. Symbolic Comput., 19:577--584, 1995.

Digital Library

[36]

C. C. Sims. Computation with permutation groups. In Proc. Second Symp. on Symbolic and Algebraic Manipulation. ACM Press, 1971.

Digital Library

[37]

C. C. Sims. How to construct a baby monster. In M. Collins, editor, Finite simple groups II, pages 339--345. (Durham 1978), Academic Press, 1980.

[38]

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.

[39]

M. Weller. Construction of large permutation representations for matrix groups ii. Applicable Algebra in Engineering, Communication and Computing, 11:463--488, 2001.

[40]

M. Weller. Computer aided existence proof of Thompson's sporadic simple group. manuscript, 2003.

[41]

R. Wilson. Atlas of finite group representations. http://www.mat.bham.ac.uk/atlas.

Cited By

Slavici VDong XKunkle DCooperman GKoepf W(2010)Fast multiplication of large permutations for disk, flash memory and RAMProceedings of the 2010 International Symposium on Symbolic and Algebraic Computation10.1145/1837934.1838001(355-362)Online publication date: 25-Jul-2010
https://dl.acm.org/doi/10.1145/1837934.1838001
Kunkle DCooperman G(2009)Harnessing parallel disks to solve Rubik's cubeJournal of Symbolic Computation10.1016/j.jsc.2008.04.01344:7(872-890)Online publication date: 1-Jul-2009
https://dl.acm.org/doi/10.1016/j.jsc.2008.04.013
Robinson EKunkle DCooperman GMaza M(2007)A comparative analysis of parallel disk-based Methods for enumerating implicit graphsProceedings of the 2007 international workshop on Parallel symbolic computation10.1145/1278177.1278190(78-87)Online publication date: 27-Jul-2007
https://dl.acm.org/doi/10.1145/1278177.1278190
Show More Cited By

Index Terms

A parallel architecture for disk-based computing over the Baby Monster and other large finite simple groups
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Algebraic algorithms

Recommendations

A disk-based parallel implementation for direct condensation of large permutation modules
ISSAC '07: Proceedings of the 2007 international symposium on Symbolic and algebraic computation

Through the use of a new disk-based method for enumerating very large orbits, condensation for orbits with tens of billions of elements can be performed. The algorithm is novel in that it offers efficient access to data using distributed disk-based data ...
On the permutation groups of cyclic codes

We classify the permutation groups of cyclic codes over a finite field. As a special case, we find the permutation groups of non-primitive BCH codes of prime length. In addition, the Sylow p-subgroup of the permutation group is given for many cyclic ...
Parametrization of self-dual codes by orthogonal matrices

We study the orthogonal group O"m of mxm matrices over the field of two elements and give applications to the theory of binary self-dual codes. We show that O"2"n acts transitively on the self-dual codes of length 2n. The subgroup O"2"n^(^1^), ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSAC '06: Proceedings of the 2006 international symposium on Symbolic and algebraic computation

July 2006

374 pages

ISBN:1595932763

DOI:10.1145/1145768

General Chair:
Barry Trager
IBM T.J. Watson Research Center, USA

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 July 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ISSAC06

Sponsor:

ISSAC06: International Symposium on Symbolic and Algebraic Computation

July 9 - 12, 2006

Genoa, Italy

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
156
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Slavici VDong XKunkle DCooperman GKoepf W(2010)Fast multiplication of large permutations for disk, flash memory and RAMProceedings of the 2010 International Symposium on Symbolic and Algebraic Computation10.1145/1837934.1838001(355-362)Online publication date: 25-Jul-2010
https://dl.acm.org/doi/10.1145/1837934.1838001
Kunkle DCooperman G(2009)Harnessing parallel disks to solve Rubik's cubeJournal of Symbolic Computation10.1016/j.jsc.2008.04.01344:7(872-890)Online publication date: 1-Jul-2009
https://dl.acm.org/doi/10.1016/j.jsc.2008.04.013
Robinson EKunkle DCooperman GMaza M(2007)A comparative analysis of parallel disk-based Methods for enumerating implicit graphsProceedings of the 2007 international workshop on Parallel symbolic computation10.1145/1278177.1278190(78-87)Online publication date: 27-Jul-2007
https://dl.acm.org/doi/10.1145/1278177.1278190
Robinson EMüller JCooperman GWang D(2007)A disk-based parallel implementation for direct condensation of large permutation modulesProceedings of the 2007 international symposium on Symbolic and algebraic computation10.1145/1277548.1277591(315-322)Online publication date: 29-Jul-2007
https://dl.acm.org/doi/10.1145/1277548.1277591

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten