INTEGER MATRIX DIAGONALIZATION

We consider algorithms for computing the Smith normal form of integer matrices. A variety of different strategies have been proposed, primar ily aimed at avoiding the major obstacle that occurs in such computati ons-explosive growth in size of intermediate entries. We present a new algorithm with excellent performance. We investigate the complexity o f such computations, indicating relationships with NP-complete problem s. We also describe new heuristics which perform well in practice. Wie present experimental evidence which shows our algorithm outperforming previous methods. (C) 1997 Academic Press Limited.