## 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 B_{k} 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 language | English |
---|---|

Pages (from-to) | 183-200 |

Number of pages | 18 |

Journal | Linear Algebra and Its Applications |

Volume | 613 |

DOIs | |

State | Published - 15 Mar 2021 |

### Bibliographical note

Funding Information:Hyang-Sook Lee was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT: Ministry of Science and ICT) (No. NRF-2018R1A2A1A05079095 ) and partially supported by the Ministry of Education (No. NRF-2019R1A6A1A11051177 ). Seongan Lim was supported by the National Research Foundation of Korea grant funded by the Korea government (No. NRF-2016R1D1A1B01008562 and NRF-2018R1A2A1A05079095 ). Gook Hwa Cho was supported by the National Research Foundation of Korea grant funded by the Korea government (No. NRF-2018R1D1A1B07041716 and NRF-2019R1A6A1A11051177 ).

Publisher Copyright:

© 2020 Elsevier Inc.

## Keywords

- Hermite Normal Form
- LLL algorithm
- Lattice