Welcome to the resource topic for 2024/2089
Title:
Computing the Hermite Normal Form: A Survey
Authors: Leon Damer
Abstract:The Hermite Normal Form (HNF) of a matrix is an analogue of the echolon form over the integers. Any integer matrix can be transformed into its unique HNF.
A common obstacle in computing the HNF is the extensive blow up of intermediate values. As first approach to this problem, we discuss the Modulo Determinant Algorithm. It keeps the entries bounded by d, the determinant of the lattice, and has a time complexity of \mathcal{O}(n^3\log^2 d), where n is the dimension of the matrix. Although this algorithm is very useful if the determinant is small, in the general case, the entries still become extremely large.
Secondly, we study the Linear Space Algorithm. It has a time complexity of \mathcal{O}(n^5\mathrm{polylog}(M, n)), where M denotes the largest absolute value of the input matrix. This is as fast as the best previously known algorithms, but in contrast, it assures space complexity linear in the input size, i.e. \mathcal{O}(n^2\log M).
As last algorithm to compute the HNF we analyze the Heuristic Algorithm, which is based on the first two algorithms. It achieves a much faster runtime in practice, yielding a heuristic runtime of \mathcal{O}(n^4\mathrm{polylog}(M, n)), while keeping the linear space complexity.
Besides some performance speed ups, the Linear Space Algorithm and Heuristic Algorithm are precisely the algorithms implemented by SageMath.
ePrint: https://eprint.iacr.org/2024/2089
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .