### Subresultants and Reduced Polynomial Remainder SequencesSubresultants and Reduced Polynomial Remainder Sequences

Access Restriction
Subscribed

 Author Collins, George E. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1967 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract Let @@@@ be an integral domain, P(@@@@) the integral domain of polynomials over @@@@. Let $\textit{P},$ $\textit{Q}$ ∈ P(@@@@) with $\textit{m}$ @@@@ deg $(\textit{P})$ ≥ $\textit{n}$ = deg $(\textit{Q})$ > 0. Let $\textit{M}$ be the matrix whose determinant defines the resultant of $\textit{P}$ and $\textit{Q}.$ Let $\textit{Mij}$ be the submatrix of $\textit{M}$ obtained by deleting the last $\textit{j}$ rows of $\textit{P}$ coefficients, the last $\textit{j}$ rows of $\textit{Q}$ coefficients and the last $2\textit{j}+1$ columns, excepting column $\textit{m}$ — $\textit{n}$ — $\textit{i}$ — $\textit{j}$ (0 ≤ $\textit{i}$ ≤ $\textit{j}$ < $\textit{n}).$ The polynomial $\textit{Rj}(\textit{x})$ = $∑\textit{i}\textit{i}=0$ det $(\textit{Mij})\textit{xi}$ is the j-t subresultant of $\textit{P}$ and $\textit{Q},$ $\textit{R0}$ being the resultant. If $\textit{b}$ = $£(\textit{Q}),$ the leading coefficient of $\textit{Q},$ then exist uniquely $\textit{R},$ $\textit{S}$ ∈ P(@@@@) such that $\textit{b}\textit{m-n}+1$ $\textit{P}$ = $\textit{QS}$ + $\textit{R}$ with deg $(\textit{R})$ < $\textit{n};$ define $R(\textit{P},$ $\textit{Q})$ = $\textit{R}.$ Define $\textit{Pi}$ ∈ $P(\textit{F}),$ $\textit{F}$ the quotient field of @@@@, inductively: $\textit{P}1$ = $\textit{P},$ $\textit{P}2$ = $\textit{Q},$ $\textit{P}3$ = $R\textit{P}1,$ $\textit{P}2$ $\textit{P}\textit{i}-2$ = $R(\textit{Pi},$ $\textit{P}\textit{i}+1)/\textit{c}δ\textit{i}-1+1\textit{i}$ for $\textit{i}$ ≥ $\textit{2}$ and $\textit{n}\textit{i}+1$ > 0, where $\textit{c}\textit{i}$ = $£(\textit{Pi}),$ $\textit{ni}$ = deg $(\textit{Pi})$ and $δ\textit{i}$ = $\textit{ni}$ — $\textit{n}\textit{i}+1.$ $\textit{P}1,$ $\textit{P}2,$ …, $\textit{Pk},$ for $\textit{k}$ ≥ 3, is called a reduced polynomial remainder sequence. Some of the main results are: (1) $\textit{Pi}$ ∈ P(@@@@) for 1 ≤ $\textit{i}$ ≤ $\textit{k};$ (2) $\textit{Pk}$ = ± $\textit{AkR}\textit{n}\textit{k}-1-1,$ when $\textit{Ak}$ = $&Pgr;\textit{k}-2\textit{i}-2\textit{c}δ\textit{i}-1(δ\textit{i}-1)\textit{i};$ (3) $\textit{c}δ\textit{k}-1-1\textit{k}$ $\textit{Pk}$ = $±\textit{A}\textit{k}+1\textit{R}\textit{n}\textit{k};$ (4) $\textit{Rj}$ = 0 for $\textit{nk}$ < $\textit{j}$ < $\textit{n}\textit{k}-1$ — 1. Taking @@@@ to be the integers $\textit{I},$ or $P\textit{r}(\textit{I}),$ these results provide new algorithms for computing resultant or greatest common divisors of univariate or multivariate polynomials. Theoretical analysis and extensive testing on a high-speed computer show the new g.c.d. algorithm to be faster than known algorithms by a large factor. When applied to bivariate polynomials, for example this factor grows rapidly with the degree and exceeds 100 in practical cases. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1967-01-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 14 Issue Number 1 Page Count 15 Starting Page 128 Ending Page 142

#### Open content in new tab

Source: ACM Digital Library