A linear space algorithm for computing the Hermite normal form

Authors: Daniele Micciancio and Bogdan Warinschi

International Symposium on Symbolic and Algebraic Computation - ISSAC 2001. July 18-21, 2001, London, Canada, pp. 231-236.

[BibTeX] [PostScript] [PDF]

Abstract: Computing the Hermite Normal Form of an n-by-n integer matrix using the best current algorithms typically requires $O\left(n^3\log M\right)$ space, where M is a bound on the length of the columns of the input matrix. Although polynomial in the input size (which is $O\left(n^2\log M\right)$ ) space (i.e., essentially the same as the input size). When implemented using standard integer arithmetic, our algorithm has the same time complexity of the asymptotically fastest (but space inefficient) algorithms. We also suggest simple heuristics that when incorporated in our algorithm result in essentially the same asymptotic running time of the theoretically fastest solutions, still maintaining our algorithm extremely practical.

Notes

Preliminary version in Electronic Colloqium on Computational Complexity, ECCC Report TR00-074, 2000