On the complexity of the Lickteig-Roy subresultant algorithm (Q1757020): Difference between revisions

Let $A$ be a commutative ring with unity endowed with a partially defined division; i.e. if $a$ and $b$ are two elements in $A$ such that $b$ divides $a$ then there is a routine to return $a/b$. Let $F,G\in A[x]$ be two polynomials. For any $0\le k <\min\{\deg(F),\deg(G)\}$, we denote by $s_k\in A$ (resp. $S_k\in A[x]$) the $k$-th subresultant coefficient (resp. $k$-th subresultant polynomial) of $F$ and $G$. The subresultant polynomial $S_k$ is said to be defective if its degree is strictly less than $k$. \par In [Calcolo 33, No. 3--4, 337--351 (1996; Zbl 0904.65024)], \textit{T. Lickteig} and \textit{M.-F. Roy} introduced a fast ``divide and conquer'' variant of the subresultant algorithm which avoids coefficient growth in defective cases. The paper under review presents the complexity analysis of Lickteig-Roy's algorithm over $A$. The obtained complexity bound is essentially the same as the classic bound in the case that $A$ is an effective field. As a consequence new convenient complexity bounds for gcds are obtained.