TR00-074 Authors: Daniele Micciancio, Bogdan Warinschi

Publication: 14th September 2000 05:44

Downloads: 4677

Keywords:

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.