# Three New Methods for Computing Subresultant Polynomial Remainder Sequences (PRS’S)

• Volume: 9, Issue: 1, page 1-26
• ISSN: 1312-6555

top

## Abstract

top
Given the polynomials f, g ∈ Z[x] of degrees n, m, respectively, with n > m, three new, and easy to understand methods — along with the more efficient variants of the last two of them — are presented for the computation of their subresultant polynomial remainder sequence (prs). All three methods evaluate a single determinant (subresultant) of an appropriate sub-matrix of sylvester1, Sylvester’s widely known and used matrix of 1840 of dimension (m + n) × (m + n), in order to compute the correct sign of each polynomial in the sequence and — except for the second method — to force its coefficients to become subresultants. Of interest is the fact that only the first method uses pseudo remainders. The second method uses regular remainders and performs operations in Q[x], whereas the third one triangularizes sylvester2, Sylvester’s little known and hardly ever used matrix of 1853 of dimension 2n × 2n. All methods mentioned in this paper (along with their supporting functions) have been implemented in Sympy and can be downloaded from the link http://inf-server.inf.uth.gr/~akritas/publications/subresultants.py

## How to cite

top

Akritas, Alkiviadis. "Three New Methods for Computing Subresultant Polynomial Remainder Sequences (PRS’S)." Serdica Journal of Computing 9.1 (2015): 1-26. <http://eudml.org/doc/281368>.

@article{Akritas2015,
abstract = {Given the polynomials f, g ∈ Z[x] of degrees n, m, respectively, with n > m, three new, and easy to understand methods — along with the more efficient variants of the last two of them — are presented for the computation of their subresultant polynomial remainder sequence (prs). All three methods evaluate a single determinant (subresultant) of an appropriate sub-matrix of sylvester1, Sylvester’s widely known and used matrix of 1840 of dimension (m + n) × (m + n), in order to compute the correct sign of each polynomial in the sequence and — except for the second method — to force its coefficients to become subresultants. Of interest is the fact that only the first method uses pseudo remainders. The second method uses regular remainders and performs operations in Q[x], whereas the third one triangularizes sylvester2, Sylvester’s little known and hardly ever used matrix of 1853 of dimension 2n × 2n. All methods mentioned in this paper (along with their supporting functions) have been implemented in Sympy and can be downloaded from the link http://inf-server.inf.uth.gr/~akritas/publications/subresultants.py},
journal = {Serdica Journal of Computing},
keywords = {Pseudo Remainders; Subresultant prs’s; Sylvester’s Matrices},
language = {eng},
number = {1},
pages = {1-26},
publisher = {Institute of Mathematics and Informatics Bulgarian Academy of Sciences},
title = {Three New Methods for Computing Subresultant Polynomial Remainder Sequences (PRS’S)},
url = {http://eudml.org/doc/281368},
volume = {9},
year = {2015},
}

TY - JOUR
TI - Three New Methods for Computing Subresultant Polynomial Remainder Sequences (PRS’S)
JO - Serdica Journal of Computing
PY - 2015
PB - Institute of Mathematics and Informatics Bulgarian Academy of Sciences
VL - 9
IS - 1
SP - 1
EP - 26
AB - Given the polynomials f, g ∈ Z[x] of degrees n, m, respectively, with n > m, three new, and easy to understand methods — along with the more efficient variants of the last two of them — are presented for the computation of their subresultant polynomial remainder sequence (prs). All three methods evaluate a single determinant (subresultant) of an appropriate sub-matrix of sylvester1, Sylvester’s widely known and used matrix of 1840 of dimension (m + n) × (m + n), in order to compute the correct sign of each polynomial in the sequence and — except for the second method — to force its coefficients to become subresultants. Of interest is the fact that only the first method uses pseudo remainders. The second method uses regular remainders and performs operations in Q[x], whereas the third one triangularizes sylvester2, Sylvester’s little known and hardly ever used matrix of 1853 of dimension 2n × 2n. All methods mentioned in this paper (along with their supporting functions) have been implemented in Sympy and can be downloaded from the link http://inf-server.inf.uth.gr/~akritas/publications/subresultants.py
LA - eng
KW - Pseudo Remainders; Subresultant prs’s; Sylvester’s Matrices
UR - http://eudml.org/doc/281368
ER -

## NotesEmbed?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.