DIMACS Series in
Discrete Mathematics and Theoretical Computer Science

VOLUME Twenty Eight
TITLE: "Groups and Computation II"
EDITORS: Larry Finkelstein, William M. Kantor
Published by the American Mathematical Society


Ordering Information

This volume may be obtained from the AMS or through bookstores in your area.

To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.

You may also visit the AMS Bookstore and order directly from there. DIMACS does not distribute or sell these books.



PREFACE


The Workshop "Groups and Computation" took place at DIMACS, the Center for Discrete Mathematics and Theoretical Computer Science on the campus of Rutgers University , on June 7-10, 1995. This, and an earlier Workshop held on Oct 7-10, 1991, aimed at merging theory and practice within the broad area of computation with groups. The primary goal of the previous Workshop was to foster a dialogue between researchers studying the computational complexity of group algorithms and those engaged in the development of practical software. It was expected that this would lead to a deeeper understanding of the mathematical issues underlying group computations, and such understanding would lead in turn to faster algorithms. Comments and subsequent work indicated that this goal had been achieved beyond our expectations. In particular, as a result of that Workshop, new collaborations formed to test the practicality of algorithms designed to meet the theoretical goal of faster asmptotic running times. Some of these have now been implemented and have been shown to have superior practical performance. The second Workshop was designed to reinforce the progress in these directions.

The scientific program consisted of invited lectures and research announcements, as well as informal discussions and software demonstrations. The eight extended talks (by L. Babai, B. Eick, C. Leedham-Green, J. Leon, C. Miller, C. Praeger and A. Niemeyer, D. Rockmore, and M. Schonert) discussed randomization, permutation groups, matrix groups, software systems, fast Fourier transforms and their applicaitons to signal processing and data analysis, computations with finitely presented goups, as well as implementation and complexity questions. These topics were also discussed further talks, as were additional ones such as group-theoretic computation with graphs, algorithms for permutation groups, properties of simple groups, and parallel architectures for matix goup computation. As in the previous Workshop, speakers ranged from established researchers to graduate students. The present Proceedings contains papers base on most, but not all, of their talks.

Software provided by the participants was available during the entire workshop and was discussed in a number of talks. One evening was devoted to informal software presentations using various systems, including numerous demonstrations by participants using GAP or Magma. In addition, there was a panel discussion whose theme was "Problems whose current algorithmic solutions are, in practice either too time- or space-consuming". The panelists (G. Cooperman, G. Havas, J. Leon, J. Neubuser, M. Schonert and L. Soicher) were selected for their broad experience in building software for group computation.

What was most striking throughout the Workshop was the convergence of theory and practice begun at the first Workshop. Almost every talk concerning practical algorithms mentioned complexity issues; almost every talk focused on complexity mentioned practical considerations. This was particulary evident when it came to research on algorithms for computing with matrix goups. In contrast with the situation for permutation groups, finite matrix groups are too "large", from both a practical and a theoretical standpoint. As a result, very few computational problems for matrix groups have polynomial-time solutions (this is true even for simple-sounding problems such as finding the order of a matrix group). Particularly fascinating are the mathematical issues that have emerged as part of the search for reasonably efficient matrix goup algorithms. The Proceedings contains several papers along these lines. The remarkable progress that has been achieved so far makes extenxive use of the classification of finite simple groups, of randomized methods, and of polynomial computation using classical Symbolic Algebra methods. This progress could not have been predicted following the first DIMACS Workshop, which was dominated by permutation groups rather than matirx groups.

The first DIMACS Workshop came into being due to the formidable efforts of Danny Gorenstein, and hence the second one also owes much to him. We are grateful for the assistance of our co-organizer Charles Sims, and to the DIMACS staff for helping the workshop to function smoothly. Christine Thierviege of the American Mathemtaical Society provided invaluable assisance in the production of this Proceedings. Finally, we would like to thank DIMACS, the National Science Foundation, the National Security Agency and Rutgers University for their financial support of the workshop.

Larry Finkelstein
William M. Kantor


TABLE OF CONTENTS

Foreward ix
Preface xi
Workshop Program xiii
Participants xv
Randomization in group algorithms: Conceptual questions

    Laszlo Babai

1
Experimenting and computing with infinite groups

    Gilbert Baumslag, Charles F. Miller III

19
Towards polynomial time algorithms for matrix groups

    Robert Beals

31
Calculating the order of an invertible matrix

    Frank Celler, C.R. Leedham-Green

55
A non-constructive recognition algorithm for the special linear and other classical groups

    Frank Celler, C.R. Leedham-Green

61
GAP/MPI: Facilitating parallelism

    Gene Cooperman

69
Constructive recognition of a black box group isomorphic to GL9n,2)

    Gene Cooperman, Larry Finkelstein, Steve Linton

85
Special presentations for the finite soluble groups and computing (pre-) Frattini subgroups

    Bettina Eick

101
Algorithms for group actions applied to graph generation

    Thomas Gruner, Reinhard Laue, Markus Meringer

113
Partitions, refinements, and permutation group computation

    Jeffrey S. Leon

123
A polycyclic quotient algorithm

    Eddie H. Lo

159
Computing the Fitting subgoup and solvable radical for small-base permutation groups in nearly linear time

    Eugene M. Luks, Akos Seress

169
Generalized FFT's- A survey of some recent results

    David K. Maslen, Daniel M. Rockmore

183
The complixity of McKay's canonical labeling algorithm

    Takunari Miyazaki

239
On nearly linear time algorithms for Sylow subgoups of small base permutation groups

    Prabhav Morje

257
Implementing a recognition algorithm for classical groups

    Alice C. Niemeyer, Cheryl E. Praeger

273
Algorithms for polycyclic-by-finite matrix groups

    Gretchen Ostheimer

297
Asymptotic results for simple groups and some applications

    Laszlo Pyber

309
Some applications of generalized FFT's

    Daniel N. Rockmore

329
Computing permutation representations for matrix groups in parallel environments

    Michael Tselman

371


Index Index of Volumes
DIMACS Homepage
Contacting the Center
Document last modified on October 28, 1998.