A cubic algorithm for computing the Hermite normal form of a nonsingular integer matrix

Abstract

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^3(\log n+\log ||A||{)}^2(\log n{)}^2)$ 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^3\log ||A||{)}^{1+o(1)}$ bit operations, where the exponent $"+o(1)"$ captures additional factors $c_1(\log n{)}^{c_2}(\log \log ||A||{)}^{c_3}$ for positive real constants $c_1,c_2,c_3$.

36 pages