RECOGNIZING BADLY PRESENTED Z-MODULES

Finitely generated Z-modules have canonical decompositions. When such modules are given in a finitely presented form, there is a classical a lgorithm for computing a canonical decomposition. This is the algorith m for computing the Smith normal form of an integer matrix. We discuss algorithms for Smith-normal-form computation, and present practical a lgorithms which give excellent performance for modules arising from ba dly presented abelian groups. We investigate such issues as congruenti al techniques, sparsity considerations, pivoting strategies for Gauss- Jordan elimination, lattice basis reduction, and computational complex ity. Our results, which are primarily empirical, show dramatically imp roved performance on previous methods.