Subresultant Polynomial Remainder Sequences Obtained by Polynomial Divisions in Q[x] or in Z[x]

Akritas, Alkiviadis G. ; Malaschonok, Gennadi I. ; Vigklas, Panagiotis S.

Serdica Journal of Computing, Tome 10 (2016) no. 3-4, pp. 197-217

Résumé

In this paper we present two new methods for computing the subresultant polynomial remainder sequence (prs) of two polynomials f, g ∈ Z[x]. We are now able to also correctly compute the Euclidean and modified Euclidean prs of f, g by using either of the functions employed by our methods to compute the remainder polynomials. Another innovation is that we are able to obtain subresultant prs’s in Z[x] by employing the function rem(f, g, x) to compute the remainder polynomials in [x]. This is achieved by our method subresultants_amv_q (f, g, x), which is somewhat slow due to the inherent higher cost of com- putations in the field of rationals. To improve in speed, our second method, subresultants_amv(f, g, x), computes the remainder polynomials in the ring Z[x] by employing the function rem_z(f, g, x); the time complexity and performance of this method are very competitive. Our methods are two different implementations of Theorem 1 (Section 3), which establishes a one-to-one correspondence between the Euclidean and modified Euclidean prs of f, g, on one hand, and the subresultant prs of f, g, on the other. By contrast, if – as is currently the practice – the remainder polynomi- als are obtained by the pseudo-remainders function prem(f, g, x) 3 , then only subresultant prs’s are correctly computed. Euclidean and modified Eu- clidean prs’s generated by this function may cause confusion with the signs and conflict with Theorem 1. ACM Computing Classification System (1998): F.2.1, G.1.5, I.1.2.

Détail

Keywords: Euclidean Algorithm, Euclidean Polynomial Remainder Sequence (prs), Modified Euclidean (Sturm’s) prs, Subresultant prs, Modified Subresultant prs, Sylvester Matrices, Bezout Matrix, Van Vleck’s Method, sympy