# 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 (2016)

- Volume: 10, Issue: 3-4, page 197-217
- ISSN: 1312-6555

## Access Full Article

top## Abstract

top## How to cite

topAkritas, 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 -

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.