Fraction-free row reduction of matrices of skew polynomials
Bernhard Beckermann, Howard Cheng, George Labahn · 2002
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 matrices of skew polynomials. The algorithm is intended 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. This allows us to obtain a polynomial-time algorithm: for an m x s matrix of input skew polynomials of degree N with coefficients whose lengths are bounded by K the algorithm has a worst case complexity of O(m5s4N4K2) bit operations.