Asymptotically fast computation of Hermite normal forms of integer matrices

Abstract

This paper presents a new algorithm for computing the Hermite normal form H of an A c Z "m of rank m together with a unimodular pre-multiplier matrix U such that UA = H. Our algorithm requires O-(m '-lnM(mlog[lAl\)) bit oper@ions to produce both H and U. Here, IIAII = max,j lAij [, M(t) bit operations are sufficient to multiply two (t] -bit integers, and 0 is the exponent for matrix multiplication over rings: two m x m matrices over a ring R can be multiplied in O(me ) ring operations from R, The previously fastest algorithm of Hafner & McCurley requires 0-(m2nM (m log I IAI [)) bit operations to produce H, but does not produce a unimodular matrix U which satisfies UA = H. Previous methods require on the order of 0-(n3M(m log I[Al 1)) bit operations to produce a U -our algorithm improves on this significantly in both a theoretical and practical sense. 1