期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2000
卷号：2000
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Computing the Hermite Normal Form
of an nn matrix using the best current algorithms typically
requires O(n3logM) 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(n2logM)),
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(n2logM) 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.
