Storage efficient algorithm for Hermite Normal Form using LLL

Gook Hwa Cho, Hyang Sook Lee, Seongan Lim, Yoonjeong Kim

Research output: Contribution to journalArticlepeer-review

Abstract

Computing HNF has a long history, but designing a storage efficient algorithm is a challenging issue for matrices of large sizes. One of the main challenges in the design of storage efficient HNF algorithm is to control the rank and the size of the intermediate input. In our proposed algorithm, we use a multiple extended gcd algorithm and show that the rank of the intermediate input matrix decreases as the number of iteration increases. The determinant of the intermediate input matrix of our algorithm is a factor of the determinant d of the input matrix and thus size reduction modulo d can be done in the computations of our algorithm. By using a lattice reduction algorithm and a proven quality of LLL reduced basis, we prove that the storage of the intermediate input matrix Bk of our algorithm is less than [Formula presented] in bits. Therefore, it is expected that a smaller storage for kth iteration is required as k closes to n. We compare the intermediate computations of our algorithm to MW-type algorithm which has an optimal asymptotic space requirement. Our experimental example and results on intermediate size suggest that the intermediate storage of our HNF algorithm is comparable to MW-type algorithm and well controlled by the intermediate input size.

Original languageEnglish
Pages (from-to)183-200
Number of pages18
JournalLinear Algebra and Its Applications
Volume613
DOIs
StatePublished - 15 Mar 2021

Keywords

  • Hermite Normal Form
  • Lattice
  • LLL algorithm

Fingerprint

Dive into the research topics of 'Storage efficient algorithm for Hermite Normal Form using LLL'. Together they form a unique fingerprint.

Cite this