A linear space algorithm for computing the hermite normal form

摘要

Computing the Hermite Normal Form of an n × n integer matrix using the best current algorithms typically requires &Ogr;(n³ log M) space, where M is a bound on the entries of the input matrix. Although polynomial in the input size (which is &Ogr;(n² log M)), this space blow-up can easily become a serious issue in practice when working on big integer matrices. In this paper we present a new algorithm for computing the Hermite Normal Form which uses only &Ogr;(n² log M) space (i.e., essentially the same as the input size). When implemented using standard algorithms for integer and matrix multiplication, our algorithm has the same time complexity of the asymptotically fastest (but space inefficient) algorithms. We also present a heuristic algorithm for HNF that achieves a substantial speedup when run on randomly generated input matrices.