  Let R=F[D;sigma,delta] be the ring of Ore polynomials over a field (or skew
field) F, where sigma is a automorphism of F and delta is a sigma-derivation.
Given a an m by n matrix A over R, we show how to compute the Hermite form H of
A and a unimodular matrix U such that UA=H. The algorithm requires a polynomial
number of operations in F in terms of both the dimensions m and n, and the
degree of the entries in A. When F=k(z) for some field k, it also requires time
polynomial in the degree in z, and if k is the rational numbers Q, it requires
time polynomial in the bit length of the coefficients as well. Explicit
analyses are provided for the complexity, in particular for the important cases
of differential and shift polynomials over Q(z). To accomplish our algorithm,
we apply the Dieudonne determinant and quasideterminant theory for Ore
polynomial rings to get explicit bounds on the degrees and sizes of entries in
H and U.
