Skip to main content

A Linear Space Algorithm for Computing the Hermite Normal Form

Daniele Micciancio, Bogdan Warinschi, A Linear Space Algorithm for Computing the Hermite Normal Form . International Symposium on Symbolic Algebraic Computation -- ISSAC'01),, pp. 231–236. February 2001. No electronic version available.

Abstract

Computing the Hermite Normal Form of an $n\times n$ integer matrix using the best current algorithms typically requires $O(n^3\log M)$ space, where $M$ is a bound on the entries of the input matrix. Although polynomial in the input size (which is $O(n^2\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 $O(n^2\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.

Bibtex entry.

Contact details

Publication Admin