Integer matrix diagonalization
George Havas and Bohdan S. Majewski

Abstract. We consider algorithms for computing the Smith normal form of 
integer matrices. Various different strategies have been proposed, primarily
trying to avoid the major obstacle that occurs in such computations - explosive
growth in size of intermediate entries. We present a new algorithm with
excellent performance.

We investigate the complexity of such computations, indicating relationships
with NP-complete problems. We also describe new heuristics which perform well
in practice. We present experimental evidence which shows our algorithm
outperforming the previous methods.