97-44: Practical Algorithms for Polycyclic Matrix Groups

DIMACS TR: 97-44

Practical Algorithms for Polycyclic Matrix Groups

Author: Gretchen Ostheimer

ABSTRACT
Many fundamental problems are undecidable for infinite matrix groups. Polycyclic matrix groups represent a large class of groups for which these same problems are known to be decidable. In this paper we describe a suite of new algorithms for studying polycyclic matrix groups --- algorithms for testing membership and for uncovering the polycyclic structure of the group. We also describe an algorithm for deciding whether or not a group is solvable, which, in the important context of subgroups of GL(n,Z), is equivalent to deciding whether or not a group is polycyclic. In contrast to previous algorithms, the algorithms in this paper are practical: experiments show that they are efficient enough to be useful in studying some reasonably complex examples using current technology.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-44.ps.gz

DIMACS Home Page