Article

A disk-based parallel implementation for direct condensation of large permutation modules

Authors:

Jürgen Müller,

Gene CoopermanAuthors Info & Claims

ISSAC '07: Proceedings of the 2007 international symposium on Symbolic and algebraic computation

Pages 315 - 322

https://doi.org/10.1145/1277548.1277591

Published: 29 July 2007 Publication History

Abstract

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 structures. This provides fast access to hundreds of gigabytes of data,which allows for computing without worrying about memory limitations.

The new algorithm is demonstrated on one of the long-standing open problems in the Modular Atlas Project [11]: the Brauer tree of the principal 17-block the sporadic simple Fischer group Fi₂₃ The tree is completed by computing three orbit counting matrices for the Fi₂₃ orbit of size 11, 739, 046, 176 acting on vectors of dimension 728 over GF (2). The construction of these matrices requires 3-1/2 days on a cluster of 56 computers,and uses 8 GB of disk storage and 800 MB of memory per machine.

References

[1]

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

Digital Library

[2]

J.H. Conway, R.T. Curtis, S.P. Norton, R.A. Parker, and R.A. Wilson. Atlas of finite groups Clarendon Press, Oxford, 1985.

[3]

G. Cooperman. STAR/MPI: Binding a parallel library to interactive symbolic algebra systems. In Proc. of International Symposium on Symbolic and Algebraic Computation (ISSAC'95) volume 249 of Lecture Notes in Control and Information Sciences pages 126--132. ACM Press, 1995. software at URL: http://www.ccs.neu.edu/home/gene/software.html\#starmpi and http://www.ccs.neu.edu/home/gene/pargcl.html

Digital Library

[4]

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

Digital Library

[5]

G. Cooperman, G. Hiss, K. Lux, and J. Müller. The Brauer tree of the principal 19-block of the sporadic simple Thompson group. Experiment. Math. 6:293--300, 1997.

[6]

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, 2003.

Digital Library

[7]

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

[8]

The GAP Group. GAP -- Groups, Algorithms, and Programming, Version 4.4 2006. http://www.gap-system.org

[9]

J. Green. Polynomial Representations of GL_n. Lecture Notes in Mathematics 830. Springer-Verlag, 1980.

[10]

G. Hiss and K. Lux. Brauer Trees of Sporadic Groups Oxford Univ. Press, Oxford, 1989.

[11]

C. Jansen, K. Lux, R. Parker, and R. Wilson. An Atlas of Brauer Characters volume11 of London Math. Soc. Monographs, (N.S.) Clarendon Press, Oxford, 1995.

[12]

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

[13]

K. Lux, J. Müller, and M. Ringe. Peakword condensation and submodule lattices: An application of the MeatAxe. J. Symb. Comp. 17:529--544, 1994.

Digital Library

[14]

J. Müller. Computational representation theory: remarks on condensation. Lecture Notes, 2003. http://www.math.rwth-aachen.de/~Juergen.Mueller/

[15]

J. Müller. On endomorphism rings and character tables. Habilitationsschrift, RWTH Aachen, 2003.

[16]

J. Müller. On the action of the sporadic simple baby monster group on the cosets of 2¹⁺²².C_o2 Preprint, 2006.

[17]

J. Müller, M. Neunhöffer, and F. Noeske. GAP 4 package orb 2006. http://www.math.rwth-aachen.de/~Max.Neunhoeffer/Computer/Software/Gap/orb.html

[18]

J. Müller, M. Neunhöffer, F. Röhr, and R. Wilson. Completing the Brauer trees for the sporadic simple Lyons group. LMS J. Comput. Math. 5:18--33, 2002.

[19]

J. Müller, M. Neunhöffer, and R. Wilson. Enumerating big orbits and an application: B acting on the cosets of Fi ₂₃ Preprint, to appear in J. Algebra, 2006. http://www.math.rwth-aachen.de/~Juergen.Mueller/

[20]

R. Parker and R. Wilson. Unpublished, 1995.

[21]

M. Ringe. The C-MeatAxe, Version 2.4, Manual RWTH Aachen, 2000.

[22]

E. Robinson and G. Cooperman. A parallel architecture for disk-based computing over the Baby Monster and other large finite simple groups. In Proc. of International Symposium on Symbolic and Algebraic Computation (ISSAC'06) pages 298--305. ACM Press, 2006.

Digital Library

[23]

J. Thackray. Modular representations of some finite groups PhD thesis, Univ. of Cambridge, 1981.

[24]

R. Wilson. Atlas of nite group representations. http://brauer.maths.qmul.ac.uk/Atlas/v3/

[25]

R. Wilson. The modular atlas homepage. http://www.math.rwth-aachen.de/homes/MOC/

[26]

R. Wilson. Standard generators for sporadic simple groups. J. Algebra 184:505--515, 1996.

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

Index Terms

A disk-based parallel implementation for direct condensation of large permutation modules
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Algebraic algorithms

Recommendations

A parallel architecture for disk-based computing over the Baby Monster and other large finite simple groups
ISSAC '06: Proceedings of the 2006 international symposium on Symbolic and algebraic computation

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 ...
Harnessing parallel disks to solve Rubik's cube

The number of moves required to solve any configuration of Rubik's cube has held a fascination for over 25 years. A new upper bound of 26 is produced. More important, a new methodology is described for finding upper bounds. The novelty is two-fold. ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSAC '07: Proceedings of the 2007 international symposium on Symbolic and algebraic computation

July 2007

406 pages

ISBN:9781595937438

DOI:10.1145/1277548

General Chair:
Dongming Wang
Beihang University and UPMC-CNRS (China/France)

Copyright © 2007 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: 29 July 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ISSAC07

Sponsor:

ISSAC07: International Symposium on Symbolic and Algebraic Computation

July 29 - August 1, 2007

Ontario, Waterloo, Canada

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
96
Total Downloads

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

Reflects downloads up to 18 Nov 2024

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

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.

Media

Figures

Other

Tables

View Table of Contents