Computing Hermite and Smith normal forms of triangular integer matrices Original Research Article

This paper considers the problem of transforming a triangular integer input matrix to canonical Hermite and Smith normal form. We provide algorithms and prove deterministic running times for both transformation problems that are optimal in the matrix dimension. The algorithms are easily implemented, assume standard integer arithmetic, and admit excellent performance in practice. The results presented here lead to a faster algorithm for computing the Smith normal form of an arbitrary (i.e. non-triangular) input matrix.