Complexity of the Havas, Majewski, Matthews LLL Hermite Normal Form Algorithm

摘要

We consider the complexity of the LLL HNF algorithm (Havas et al., 1998, Algorithm 4). This algorithm takes as input an m by n matrix G of integers and produces as output A matrix b∈bG is in Hermite normal form (upside down). The analysis is similar to that of an extended LLL algorithm as given in van der Kallen (1998).