Abstract

We present a new algorithm for row reduction of a matrix of skew polynomials. The algorithm can be used for finding full rank decompositions and other rank revealing transformations of such matrices. In particular these reductions can be applied to problems such as the desingularization of linear recurrence systems and for computing rational solutions of a large class of linear functional systems. The algorithm is suitable for computation in exact arithmetic domains where the growth of coefficients in intermediate computations is a central concern. This coefficient growth is controlled by using fraction-free methods. At the same time the method is fast: for an $m times s$ matrix of input skew polynomials of degree $N$ with coefficients bounded by $K$ the algorithm has a worst case complexity of $O(m^5 s^4 (N+1)^4 K^2)$ bit operations.