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.6 n  log 2   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.
['Gene Cooperman', 'Larry Finkelstein', 'Bryant W. York', 'Michael Tselman']
Constructing permutation representations for large matrix groups