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

Akritas, Alkiviadis G., Malaschonok, Gennadi I., and Vigklas, Panagiotis S.. "Subresultant Polynomial Remainder Sequences Obtained by Polynomial Divisions in Q[x] or in Z[x]." Serdica Journal of Computing 10.3-4 (2016): 197-217. <http://eudml.org/doc/289510>.

@article{Akritas2016,
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.},
author = {Akritas, Alkiviadis G., Malaschonok, Gennadi I., Vigklas, Panagiotis S.},
journal = {Serdica Journal of Computing},
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},
language = {eng},
number = {3-4},
pages = {197-217},
publisher = {Institute of Mathematics and Informatics Bulgarian Academy of Sciences},
title = {Subresultant Polynomial Remainder Sequences Obtained by Polynomial Divisions in Q[x] or in Z[x]},
url = {http://eudml.org/doc/289510},
volume = {10},
year = {2016},
}

TY - JOUR
AU - Akritas, Alkiviadis G.
AU - Malaschonok, Gennadi I.
AU - Vigklas, Panagiotis S.
TI - Subresultant Polynomial Remainder Sequences Obtained by Polynomial Divisions in Q[x] or in Z[x]
JO - Serdica Journal of Computing
PY - 2016
PB - Institute of Mathematics and Informatics Bulgarian Academy of Sciences
VL - 10
IS - 3-4
SP - 197
EP - 217
AB - 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.
LA - eng
KW - 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
UR - http://eudml.org/doc/289510
ER -