For such a group G, we are able in polynomial time to compute a homomorphism phi such that phi(G) is a finite matrix group and the kernel of phi is solvable. If in addition G has a nilpotent subgroup of finite index, we obtain much stronger results. These include an effective encoding of elements of G such that the encoding length of an element obtained as a product of length L over the generators is 0(log L) times a polynomial in the input length. This result is the best possible; it has been shown by Tits and Wolf that if a finitely generated matrix group does not have a nilpotent subgroup of finite index, then the number of group elements expressible as words of length L over the generators grows as c^L for some constant c>1 depending on G.
For groups with abelian subgroups of finite index, we obtain a Las Vegas algorithm for several basic computational tasks including membership testing and computing a presentation. This generalizes recent work of Beals and Babai, who give a Las Vegas algorithm for the case of finite groups, as well as recent work of Babai, Beals, Cai, Ivanyos, and Luks, who give a deterministic algorithm for the case of abelian groups.
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-30.ps.gz
DIMACS Home Page