Fraction-free row reduction of matrices of Ore polynomials. (Q2457346)

Let \(K[Z,\sigma,\delta]\) be a ring of Ore polynomials, where \(K\) is a field of coefficients with injective endomorphism \(\sigma\) and a derivation \(\delta\), \(Z\) is an indeterminate and the multiplication rule is \(Za=\sigma(a)Z+\delta(a)\), \(a\in K\). In the paper under review the authors consider matrices of Ore polynomials and study the problem of transforming such matrices into simpler ones using certain row operations. The primary interest is in transformations which allow for easy determination of the rank and left nullspaces. The existing algorithms have good arithmetic complexity but coefficient growth may occur and can only be controlled through coefficient GCD computations. Otherwise the coefficient growth may be exponential. Trying to solve this problem, in the present paper the authors give a fraction-free algorithm working over the domain \(D[Z,\sigma,\delta]\) with \(D\) an integral domain, \(\sigma(D)\subset D\), \(\delta(D)\subset D\). The advantage is that the coefficient growth is controlled without any need of costly coefficient GCD computations. All intermediate results can be bounded in size which allows for a precise analysis of the growth of coefficients of the computation. The authors give numerous applications especially in the case of matrices of skew polynomials. Numerical experiments show that the new algorithms are faster than the existing ones when coefficient growth is significant.