On the complexity of the Lickteig-Roy subresultant algorithm
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.
- A new method for computing polynomial greatest common divisors and polynomial remainder sequences
- Algorithme de Bareiss, algorithme des sous-résultants
- An elementary approach to subresultants theory.
- Bezout matrices, subresultant polynomials and parameters
- Cauchy index computation
- Deterministic root finding over finite fields using Graeffe transforms
- Division-free computation of subresultants using Bezout matrices
- Effective procedures in field theory
- Eine Verallgemeinerung des Sturmschen Wurzelzählverfahrens
- Euclid's Algorithm for Large Numbers
- Fast computation of continued fraction expansions.
- Fast computation of GCDs
- Fast fraction-free triangularization of Bézoutians with applications to sub-resultant chain computation
- Fast separable factorization and applications
- Fast solution of toeplitz systems of equations and computation of Padé approximants
- Faster sparse multivariate polynomial interpolation of straight-line programs
- scientific article; zbMATH DE number 1574467 (Why is no real title available?)
- scientific article; zbMATH DE number 435565 (Why is no real title available?)
- scientific article; zbMATH DE number 3922806 (Why is no real title available?)
- scientific article; zbMATH DE number 3765129 (Why is no real title available?)
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- scientific article; zbMATH DE number 3535615 (Why is no real title available?)
- scientific article; zbMATH DE number 1253989 (Why is no real title available?)
- scientific article; zbMATH DE number 480305 (Why is no real title available?)
- scientific article; zbMATH DE number 976329 (Why is no real title available?)
- scientific article; zbMATH DE number 3440002 (Why is no real title available?)
- scientific article; zbMATH DE number 1446863 (Why is no real title available?)
- Matrix computation of subresultant polynomial remainder sequences in integral domains
- Minors of Bezout matrices, subresultants and the parameterization of the degree of the polynomial greatest common divisor
- Modern computer algebra
- Modular SIMD arithmetic in \textsc{Mathemagix}
- New structure theorem for subresultants
- On computing the determinant in small parallel time using a small number of processors
- On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors
- On Euclid's Algorithm and the Theory of Subresultants
- On fast multiplication of polynomials over arbitrary algebras
- On the factorization of polynomials in a finite number of steps
- Optimizations of the subresultant algorithm
- Reduction of bivariate polynomials from convex-dense to dense, with application to factorizations
- Subresultants and Reduced Polynomial Remainder Sequences
- Subresultants revisited.
- Sylvester-Habicht sequences and fast Cauchy index computation
- The Computational Complexity of Continued Fractions
- Near-optimal computation of runs over general alphabet via non-crossing LCE queries
- Fast computation of generic bivariate resultants
- Efficient sampling in spectrahedra and volume approximation
- Subresultants of \((x-\alpha)^m\) and \((x-\beta)^n\), Jacobi polynomials and complexity
- Directed evaluation
- Fast multivariate multi-point evaluation revisited
- Accelerated tower arithmetic
- On the complexity exponent of polynomial system solving
- An Average-Case Sublinear Exact Li and Stephens Forward Algorithm
- Elimination ideal and bivariate resultant over finite fields
- High-order lifting for polynomial Sylvester matrices
- Bivariate polynomial reduction and elimination ideal over finite fields
- Efficient computation of Riemann-Roch spaces for plane curves with ordinary singularities
- Factoring sparse polynomials fast
- Computational schemes for subresultant chains
This page was built for publication: On the complexity of the Lickteig-Roy subresultant algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1757020)
