Please use this identifier to cite or link to this item: http://hdl.handle.net/10525/2924

 Title: Subresultant Polynomial Remainder Sequences Obtained by Polynomial Divisions in Q[x] or in Z[x] Authors: Akritas, Alkiviadis G.Malaschonok, Gennadi I.Vigklas, Panagiotis S. Keywords: Euclidean AlgorithmEuclidean Polynomial Remainder Sequence (prs)Modified Euclidean (Sturm’s) prsSubresultant prsModified Subresultant prsSylvester MatricesBezout MatrixVan Vleck’s Methodsympy Issue Date: 2016 Publisher: Institute of Mathematics and Informatics Bulgarian Academy of Sciences Citation: Serdica Journal of Computing, Vol. 10, No 3-4, (2016), 197p-217p Abstract: 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. URI: http://hdl.handle.net/10525/2924 ISSN: 1312-6555 Appears in Collections: Volume 10 Number 3-4

Files in This Item:

File Description SizeFormat