If a matrix group G is defined over a finite field then, provided that the group is not too large, we can construct a BSGS-representation for G and consequently apply the standard algorithms for group structure as described in Chapter MATRIX GROUPS OVER GENERAL RINGS. However, there are many examples of groups having moderately small dimension where we cannot find a BSGS-representation.
In this chapter we describe techniques for computing with matrix groups that do not assume that a BSGS-representation is available. Thus, the techniques described here apply to matrix groups possibly having much larger order or much larger dimension than those that can be handled with the techniques of Chapter MATRIX GROUPS OVER GENERAL RINGS.
The CompositionTree package introduced in Section Composition Trees for Matrix Groups, which includes the collection of LMG (large matrix group) functions described in Section The LMG functions, provides a framework for such investigations. The package was prepared by Henrik Bäärnhielm, Derek Holt, C.R. Leedham-Green and E.A. O'Brien, and includes code developed by Peter Brooksbank, Elliot Costi, Kenneth Clarkson, Heiko Dietrich, Alice Niemeyer, and Csaba Schneider.
For recent surveys of work in this area, we refer the reader to [O'B06], [O'B11].
The techniques described in this chapter fall roughly into two categories.