Subresultants and Reduced Polynomial Remainder Sequences

ABSTRACT

Let @@@@ be an integral domain, P(@@@@) the integral domain of polynomials over @@@@. Let P, Q ∈ P(@@@@) with m @@@@ deg (P) ≥ n = deg (Q) > 0. Let M be the matrix whose determinant defines the resultant of P and Q. Let Mij be the submatrix of M obtained by deleting the last j rows of P coefficients, the last j rows of Q coefficients and the last 2j+1 columns, excepting column m — n — i — j (0 ≤ i ≤ j < n). The polynomial Rj(x) = ∑ii=0 det (Mij)xi is the j-t subresultant of P and Q, R0 being the resultant. If b = £(Q), the leading coefficient of Q, then exist uniquely R, S ∈ P(@@@@) such that bm-n+1 P = QS + R with deg (R) < n; define R(P, Q) = R. Define Pi ∈ P(F), F the quotient field of @@@@, inductively: P1 = P, P2 = Q, P3 = RP1, P2 Pi-2 = R(Pi, Pi+1)/c&dgr;i-1+1i for i ≥ 2 and ni+1 > 0, where ci = £(Pi), ni = deg (Pi) and &dgr;i = ni — ni+1. P1, P2, …, Pk, for k ≥ 3, is called a reduced polynomial remainder sequence. Some of the main results are: (1) Pi ∈ P(@@@@) for 1 ≤ i ≤ k; (2) Pk = ± AkRnk-1-1, when Ak = &Pgr;k-2i-2c&dgr;i-1(&dgr;i-1)i; (3) c&dgr;k-1-1k Pk = ±Ak+1Rnk; (4) Rj = 0 for nk < j < nk-1 — 1. Taking @@@@ to be the integers I, or Pr(I), these results provide new algorithms for computing resultant or greatest common divisors of univariate or multivariate polynomials. Theoretical analysis and extensive testing on a high-speed computer show the new g.c.d. algorithm to be faster than known algorithms by a large factor. When applied to bivariate polynomials, for example this factor grows rapidly with the degree and exceeds 100 in practical cases.

REFERENCES

• 1: COLLINS, G.E. Polynomial reintinder sequences and determinani, s. Amer. Math. Mon. 73, 7 (Aug.-Sept. 1966), 708-712.
• 2: BROWN, W. S., HYDE, J. P., AND TAGUE, B.A. The ALPAK system for non-numerical algebra on a digital computer. Pt. I: Bell System Tech. J 412, 5 (Sept. 1963), 2081-2119. Pt. II: Ibid. 43, 2 (March 1964), 785-804. Pl. III: Ibid. S, 4 (July 1964), 1547-1562.
• 3: BOCHER, M. Introduclion to Higher Algebra. MacMillan Co., New York, 1907.
• 4: G. E. Collins, PM, a system for polynomial manipulation, Communications of the ACM, v.9 n.8, p.578-589, Aug. 1966 [doi>10.1145/365758.365770]
• 5: BODEWIG, E. Matrix Calculus (2nd Ed.). North-Holland Publishing Co., Amsterdam, 1959.
• 6: Leland H. Williams, Algebra of Polynomials in Several Variables for a Digital Computer, Journal of the ACM (JACM), v.9 n.1, p.29-40, Jan. 1962 [doi>10.1145/321105.321109]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Polynomials, methods for

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

General Terms:
Algorithms, Measurement, Performance, Theory, Verification