An international research project within computational group theory. The aim is to produce efficient algorithms for solving problems with matrix groups over finite fields, as well as making efficient implementations of these algorithms. The primary computer algebra system used is Magma, but GAP is also used.

The project dates back to the early 1990's, and a major goal has been
to produce an algorithm that computes a *composition tree* of a
matrix group, given by a set of generators. From a composition tree,
one can readily construct a composition series of the group, as well
as homomorphisms to the composition factors. This provides basic
structural information about the group, and also tools for further
computational tasks.

The approach for finding a composition tree is to use a divide-and-conquer strategy, by constructing a homomorphism into another group, and recursively finding a composition tree of the image and the kernel of the homomorphism. To construct homomorphisms, one uses Aschbacher's classification of the subgroups of the general linear group into 9 categories. This has led to a series of papers that present algorithms for deciding if a given matrix group lies in a specified Aschbacher category, and for constructing the corresponding homomorphism.

The base cases of the recursion are groups without proper normal
subgroups, the finite simple groups. Problems which arise in the base
cases include *constructive membership testing* and
*constructive recognition*. This has led to a series of papers
that present algorithms for these problems in various classes of the
finite simple groups.

The composition tree algorithm is probabilistic of the type known as
*one-sided Monte Carlo*. This means that there is a non-zero probability
that the constructed composition tree is incorrect, which in this case
means that it only is a composition tree for a proper subgroup. To determine
if this is the case, one can construct a presentation of the group
recursively, using presentations of the simple groups in the base
cases, and then verify that the group satisfies the presentation. In
order for this to be an efficient algorithm, the presentations of the
simple groups have to be *short presentations*. This has led to a
series of papers that present short presentations for various classes
of the finite simple groups.

More detailed information about the project up to the year 2005 can be found in this survey.

- The computational matrix group project
- Towards effective algorithms for linear groups, PDF
- Constructive recognition of PSL(2,q), PDF
- Writing projective representations over subfields, PDF
- Finding the characteristic of a group of Lie type, PDF
- Constructive recognition of SL(3,q), PDF
- Recognising tensor-induced matrix groups, PDF
- Recognising tensor products of matrix groups, PDF
- Computing matrix group decompositions with respect to a normal subgroup, PDF
- Testing matrix groups for primitivity, PDF
- Selecting base points for the Schreier-Sims algorithm for matrix groups, PDF
- Constructive recognition of finite alternating and symmetric groups acting as matrix groups on their natural permutation modules, DOI
- A black-box group algorithm for recognizing finite symmetric and alternating groups, DOI
- Fast recognition of classical groups over large fields
- A constructive recognition algorithm for the special linear group, PDF
- A non-constructive recognition algorithm for the special linear and other classical groups, PDF
- Calculating the order of an invertible matrix, PDF
- Complexity and computation in matrix groups
- A recognition algorithm for non-generic classical groups over finite fields
- A recognition algorithm for classical groups over finite fields, DOI
- Implementing a recognition algorithm for classical groups
- Computation with matrix groups over finite fields
- A recognition algorithm for special linear groups, DOI
- A reduction algorithm for matrix groups with an extraspecial normal subgroup, PDF
- Constructive recognition of normalizers of small extra-special matrix groups, DOI
- Black-box recognition of finite simple groups of Lie type by statistics of element orders, PDF
- Computing with matrix groups
- A data structure for a uniform approach to computations with finite groups, PDF
- Fast constructive recognition of a black box group isomorphic to S_n or A_n using Goldbach's conjecture, DOI
- Constructive recognition of classical groups in their natural representation, PDF
- Fast constructive recognition of black box orthogonal groups, PDF
- Fast constructive recognition of black box unitary groups, PDF
- On constructive recognition of a black box PSL(d, q), PDF
- A constructive recognition algorithm for the matrix group Omega(d, q), PDF
- Testing matrix groups for irreducibility, PS
- Recognising the Suzuki groups in their natural representations, arXiv
- Simple groups in computational group theory, PDF
- Short presentations for finite groups, PDF
- An implementation of the Neumann-Praeger algorithm for the recognition of special linear groups, PS
- Black box classical groups, PDF
- Variants of product replacement, PDF
- Generating random elements of a finite group, PDF
- Writing representations over minimal fields, DOI
- On the maximal subgroups of finite classical groups, DOI
- Small degree representations of finite Chevalley groups in defining characteristic, PDF
- Matrix generators for the Ree groups 2G2(q), PDF

- Composition tree, new version
- Chief tree
- Exceptional groups
- Classical groups natural representation, even characteristic
- Classical groups, arbitrary representation
- Short presentations

Main Magma package for computing composition trees: tar.bz2, tar.gz, zip.

Last updated 2008-06-10