Computing the Hermite form of a matrix of Ore polynomials

Let F[∂;σ,δ] be the ring of Ore polynomials over a field (or a skew field) F, where σ is an automorphism of F and δ is a σ-derivation. Given a matrix A∈F[∂;σ,δ]m×n, 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 the dimensions m and n, and the degrees (in ∂) of the entries in A. When F=k(z) for some field k, it also requires time polynomial in the degrees in z of the coefficients of the entries, and if k=Q it requires time polynomial in the bit length of the rational 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 Dieudonné determinant and quasideterminant theory for Ore polynomial rings to get explicit bounds on the degrees and sizes of entries in H and U.