Fraction-free row reduction of matrices of skew polynomials

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 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(m⁵s⁴N⁴K²) bit operations.

REFERENCES

• 1: S. Abramov. EG-eliminations. Journal of Difference Equations and Applications, 5:393-433, 1999.
• 2: Sergei A. Abramov , Manuel Bronstein, On solutions of linear functional systems, Proceedings of the 2001 international symposium on Symbolic and algebraic computation, p.1-6, July 2001, London, Ontario, Canada [doi>10.1145/384101.384102]
• 3: E. Bareiss. Sylvester's identity and multistep integer-preserving Gaussian elimination. Math. Comp., 22(103):565-578, 1968.
• 4: B. Beckermann and G. Labahn. A uniform approach for Hermite Padé and simultaneous Padé approximants and their matrix generalization. Numerical Algorithms, 3:45-54, 1992.
• 5: Bernhard Beckermann , George Labahn, A Uniform Approach for the Fast Computation of Matrix-Type Pade Approximants, SIAM Journal on Matrix Analysis and Applications, v.15 n.3, p.804-823, July 1994 [doi>10.1137/S0895479892230031]
• 6: Bernhard Beckermann , George Labahn, Recursiveness in matrix rational interpolation problems, Journal of Computational and Applied Mathematics, v.77 n.1-2, p.5-34, Jan. 13, 1997 [doi>10.1016/S0377-0427(96)00120-3]
• 7: B. Beckermann and G. Labahn. Effective computation of rational approximants and interpolants. Reliable Computing, 6:365-390, 2000.
• 8: Bernhard Beckermann , George Labahn, Fraction-Free Computation of Matrix Rational Interpolants and Matrix GCDs, SIAM Journal on Matrix Analysis and Applications, v.22 n.1, p.114-144, 2000 [doi>10.1137/S0895479897326912]
• 9: W. S. Brown , J. F. Traub, On Euclid's Algorithm and the Theory of Subresultants, Journal of the ACM (JACM), v.18 n.4, p.505-514, Oct. 1971 [doi>10.1145/321662.321665]
• 10: George E. Collins, Subresultants and Reduced Polynomial Remainder Sequences, Journal of the ACM (JACM), v.14 n.1, p.128-142, Jan. 1967 [doi>10.1145/321371.321381]
• 11: Keith O. Geddes , Stephen R. Czapor , George Labahn, Algorithms for computer algebra, Kluwer Academic Publishers, Norwell, MA, 1992
• 12: Z. Li. A Subresultant Theory for Linear Differential, Linear Difference and Ore Polynomials, with Applications. PhD thesis, Johannes Kepler Univ. Linz, Austria, 1996.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials; Computations on matrices

General Terms:
Algorithms, Measurement