# 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}\mathrm{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}\mathrm{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