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