  In this paper, a polynomial-time algorithm is given to compute the
generalized Hermite normal form for a matrix F over Z[x], or equivalently, the
reduced Groebner basis of the Z[x]-module generated by the column vectors of F.
The algorithm is also shown to be practically more efficient than existing
algorithms. The algorithm is based on three key ingredients. First, an F4 style
algorithm to compute the Groebner basis is adopted, where a novel prolongation
is designed such that the coefficient matrices under consideration have
polynomial sizes. Second, fast algorithms to compute Hermite normal forms of
matrices over Z are used. Third, the complexity of the algorithm are guaranteed
by a nice estimation for the degree and height bounds of the polynomials in the
generalized Hermite normal form.
