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

Stavros Birmpilis, George Labahn, Arne Storjohann

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 multiplicati…