Computing the Hermite Normal Form
of an $n\times n$ matrix using the best current algorithms typically
requires $O(n^3\log M)$ 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(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 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.