Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR00-074 | 12th July 2000 00:00

A Linear Space Algorithm for Computing the Hermite Normal Form


Authors: Daniele Micciancio, Bogdan Warinschi
Publication: 14th September 2000 05:44
Downloads: 2272


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.

ISSN 1433-8092 | Imprint