A Cubic Algorithm for Computing the Hermite Normal Form of a Nonsingular Integer Matrix

A Las Vegas randomized algorithm is given to compute the Hermite normal form of a nonsingular integer matrix A of dimension n . The algorithm uses quadratic integer multiplication and cubic matrix multiplication and has running time bounded by O ( n ³ (log  n + log || A ||) ² (log  n ) ² ) bit operations, where || A || = max  _ij | A _ij | denotes the largest entry of A in absolute value. A variant of the algorithm that uses pseudo-linear integer multiplication is given that has running time ( n ³ log || A ||) ^{1 + o (1)} bit operations, where the exponent `` + o (1)′′ captures additional factors \(c_1 (\log n)^{c_2} (\rm {loglog} ||A||)^{c_3} \) for positive real constants c ₁ , c ₂ , c ₃ .