BulDML at Institute of Mathematics and Informatics >
IMI Periodicals >
Serdica Journal of Computing >
2016 >
Volume 10 Number 3-4 >

Please use this identifier to cite or link to this item:

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 Algorithm
Euclidean Polynomial Remainder Sequence (prs)
Modified Euclidean (Sturm’s) prs
Subresultant prs
Modified Subresultant prs
Sylvester Matrices
Bezout Matrix
Van Vleck’s Method
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.
ISSN: 1312-6555
Appears in Collections:Volume 10 Number 3-4

Files in This Item:

File Description SizeFormat
sjc-vol10-num3-4-2016-p197-p217.pdf817.18 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0!   Creative Commons License