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 M _ij 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 2 j +1 columns, excepting column m — n — i — j (0 ≤ i ≤ j < n ). The polynomial R _j ( x ) = ∑ ⁱ _{i =0} det ( M _ij ) x ⁱ is the j-t subresultant of P and Q , R ₀ being the resultant. If b = £( Q ), the leading coefficient of Q , then exist uniquely R , S ∈ P(@@@@) such that b ^{m-n +1} P = QS + R with deg ( R ) < n ; define R( P , Q ) = R . Define P _i ∈ P( F ), F the quotient field of @@@@, inductively: P ₁ = P , P ₂ = Q , P ₃ = R P ₁ , P ₂ P _{i -2} = R( P _i , P _{i +1} )/ c ^{δ _{i -1} +1} _i for i ≥ 2 and n _{i +1} > 0, where c _i = £( P _i ), n _i = deg ( P _i ) and δ _i = n _i — n _{i +1} . P ₁ , P ₂ , …, P _k , for k ≥ 3, is called a reduced polynomial remainder sequence . Some of the main results are: (1) P _i ∈ P(@@@@) for 1 ≤ i ≤ k ; (2) P _k = ± A _k R n _{k -1} -1 , when A _k = Π ^{k -2} _{i -2} c ^{δ _{i -1} (δ i -1)} _i ; (3) c ^{δ _{k -1} -1} _k P _k = ± A _{k +1} R n _k ; (4) R _j = 0 for n _k < j < n _{k -1} — 1. Taking @@@@ to be the integers I , or P ^r ( 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.