Access Restriction

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

   Open content in new tab
Source: ACM Digital Library