Other publications | or | of 2001 |

# 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.

## Publication Admin