Asymptotically fast triangularization of matrices over rings

Abstract

We consider problems related to the computation of Hermite and Smith normal forms of integer matrices, and more generally matrices over a principal ideal ring. First, we show that if the matrix A is m × n, with rank m and integer entries bounded in absolute value by T, then the Hermite normal form can be computed in O(m2nB(m log(mT))) bit operations, where B(t) denotes a function that bounds the time required to perform the extended Euclidean algorithm on two t bit integers. Furthermore we show that the Smith normal form can be computed in O(m3nB(mlog(mT))log(mT)) bit operations.∗∗ In the second part of the paper we apply fast matrix multiplication techniques to the problem of triangularizing a matrix over a ring using elementary column operations. We also prove that matrix inversion and multiplication are equivalent in complexity over an arbitrary Principal Ideal Domain, generalizing a result of Bunch and Hopcroft. We then apply our general results to obtain an algorithm for triangularizing integer matrices that has a faster running time than the known Hermite normal form algorithms. The triangular matrix that is computed has small entries like the Hermite normal form, and will suffice for many applications. In the last part of the paper, we discuss a probabilistic method for calculating Smith normal forms.