Loading...
Please wait, while we are loading the content...
Similar Documents
A linear space algorithm for computing the Hermite
| Content Provider | CiteSeerX |
|---|---|
| Author | Micciancio, Daniele Warinschi, Bogdan |
| Description | Computing the Hermite Normal Form of an n x 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 se-rious 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 imple-mented using standard algorithms for integer and matrix multiplication, our algorithm has the same time complex-ity of the asymptotically fastest (but space inefficient) al-gorithms. We also present a heuristic algorithm for HNF that achieves a substantial speedup when run on randomly generated input matrices. 1. |
| File Format | |
| Language | English |
| Publisher Institution | Normal Form, International Symposium on Symbolic and Algebraic Computation, ACM press |
| Access Restriction | Open |
| Subject Keyword | Input Matrix Input Size Time Complex-ity New Algorithm Standard Algorithm Substantial Speedup Linear Space Algorithm Integer Matrix Hermite Normal Form Big Integer Matrix Se-rious Issue Heuristic Algorithm Current Algorithm Matrix Multiplication Space Blow-up Space Inefficient |
| Content Type | Text |
| Resource Type | Article |
