Computing bases in Hermite normal form of lattices of integer relations

Abstract

Given a full column rank $M\in {\mathbb{Z}}^{\ell \times m}$ and an $F\in {\mathbb{Z}}^{n\times m}$ we present an algorithm to compute the $n\times n$ basis in Hermite form of the integer lattice comprised of all rows $p\in {\mathbb{Z}}^{1\times n}$ such that $pF\in {\mathbb{Z}}^{1\times m}$ is in the integer lattice generated by the rows of $M$. The algorithm is randomized of the Las Vegas type, that is, it can fail with probability at most $1/2$, but if fail is not returned it guarantees to produce the correct result. When $M$ is square and $F=I_m$, then the computed basis is the Hermite normal form of $M$, and the algorithm uses about the same number of bit operations as required to multiply together two matrices of the same dimension and size of entries as $M$.