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⥈i-1+1i for i 蠅 2 and ni+1 > 0, where ci = £(Pi), ni = deg (Pi) and ⥈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 = k-2i-2c⥈i-1(⥈i-1)i; (3) c⥈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. © 1967, ACM. All rights reserved.