zbMATH — the first resource for mathematics

Integer matrix diagonalization. (English) Zbl 0880.68066
Summary: We consider algorithms for computing the Smith normal form of integer matrices. A variety of different strategies have been proposed, primarily aimed at avoiding 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 previous methods.

68W30 Symbolic computation and algebraic computation
65F30 Other matrix algorithms (MSC2010)
65Y20 Complexity and performance of numerical algorithms
15B36 Matrices of integers
15A21 Canonical forms, reductions, classification
Full Text: DOI