Asymptotically fast triangulation of matrices over rings
James Lee Hafner, Kevin S. McCurley · Symposium on Discrete Algorithms · 1990
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 {times} n, with rank m and integer entries bounded in absolute value by T, then the Hermite normal form can be computed in O(m{sup 2}nB(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(m{sup 3}nB(m log(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 timer 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.more » In the last part of the paper, we discuss a probabilistic method for calculating Smith normal forms. 17 refs.« less