On computing polynomial GCDs in alternate bases

ABSTRACT

In this paper, we examine the problem of computing the greatest common divisor (GCD) of univariate polynomials represented in different bases. When the polynomials are represented in Newton basis or a basis of orthogonal polynomials, we show that the well-known Sylvester matrix can be generalized. We give fraction-free and modular algorithms to directly compute the GCD in the alternate basis. These algorithms are suitable for computation in domains where growth of coefficients in intermediate computations are a central concern. In the cases of Newton basis and bases using certain orthogonal polynomials, we also show that the standard subresultant algorithm can be applied easily. If the degrees of the input polynomials is at most n and the degree of the GCD is at least n/2, our algorithms outperform the corresponding algorithms using the standard power basis.

REFERENCES

• 1: Milton Abramowitz, Handbook of Mathematical Functions, With Formulas, Graphs, and Mathematical Tables,, Dover Publications, Incorporated, 1974
• 2: E. Bareiss. Sylvester's identity and multistep integer-preserving Gaussian elimination. Math. Comp., 22(103):565--578, 1968.
• 3: S. Barnett. Greatest common divisors of several polynomials. Proc. Cambridge Phil. Soc., 70:263--468, 1971.
• 4: Stephen Barnett, Polynomials and Linear Control Systems, Marcel Dekker, Inc., New York, NY, 1983
• 5: S. Barnett. Division of generalized polynomials using the comrade matrix. Linear Algebra and its Applications, 60:159--175, 1984.
• 6: S. Barnett. Euclidean remainders for generalized polynomials. Linear Algebra and its Applications, 99:111--122, 1988.
• 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: W. S. Brown, On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors, Journal of the ACM (JACM), v.18 n.4, p.478-504, Oct. 1971 [doi>10.1145/321662.321664]
• 11: Stanley Cabay, Exact solution of linear equations, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.392-398, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806310]
• 12: Howard Cheng , George Labahn, Algorithms for normal forms for matrices of polynomials and ore polynomials, 2003
• 13: H. Cheng and G. Labahn. Output-sensitive modular algorithms for polynomial matrix normal forms. Submitted to J. Symbolic Computation, 2004.
• 14: 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]
• 15: Angel Díaz , Erich Kaltofen, On computing greatest common divisors with polynomials given by black boxes for their evaluations, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.232-239, July 10-12, 1995, Montreal, Quebec, Canada [doi>10.1145/220346.220375]
• 16: Gema M. Diaz-Toca , Laureano Gonzalez-Vega, Squarefree decomposition of univariate polynomials depending on a parameter. Application to the integration of parametric rational functions, Journal of Symbolic Computation, v.32 n.3, p.191-209, 09/01/2001 [doi>10.1006/jsco.2001.0471 ]
• 17: Gema M. Diaz-Toca , Laureano Gonzalez-Vega, Barnett's theorems about the greatest common divisor of several univariate polynomials through Bezout-like matrices, Journal of Symbolic Computation, v.34 n.1, p.59-81, July 2002 [doi>10.1006/jsco.2002.0542]
• 18: Joachim von zur Gathen , Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, NY, 1999
• 19: Keith O. Geddes , Stephen R. Czapor , George Labahn, Algorithms for computer algebra, Kluwer Academic Publishers, Norwell, MA, 1992
• 20: L. Gemignani. Manipulating polynomials in generalized form. 1996.
• 21: W. Habicht. Eine Verallgemeinerung des Sturmschen Wurzelzählverfahrens. Commentarii Mathematici Helvetici, 21:99--116, 1948.
• 22: Erich Kaltofen , Barry M. Trager, Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators, Journal of Symbolic Computation, v.9 n.3, p.301-320, March 1990 [doi>10.1016/S0747-7171(08)80015-6]
• 23: Z. Li. A Subresultant Theory for Linear Differential, Linear Difference and Ore Polynomials, with Applications. PhD thesis, Johannes Kepler University, 1996.
• 24: R. Loos. Generalized polynomial remainder sequences. In Computer Algebra: Symbolic and Algebraic Computation, pages 115--137. Springer-Verlag, 1982.
• 25: Bhubaneswar Mishra, Algorithmic algebra, Springer-Verlag New York, Inc., New York, NY, 1993

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
Krylov matrices, euclidean algorithm, fraction-free arithmetic, orthogonal polynomials, subresultants