On the complexity of the Lickteig-Roy subresultant algorithm
type: Item
instance of: scholarly article
title: On the complexity of the Lickteig-Roy subresultant algorithm
zbMATH Open document ID: 1409.13051
author: Grégoire Lecerf
published in: Journal of Symbolic Computation
publication date: 2018-12-28T00:00:00Z
review text: 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.
reviewed by: Amir Hashemi
Mathematics Subject Classification ID: 13P15
Mathematics Subject Classification ID: 68W30
Mathematics Subject Classification ID: 68R05
zbMATH DE Number: 6997084
zbMATH Keywords: resultant
zbMATH Keywords: subresultant
zbMATH Keywords: Euclidean sequence
zbMATH Keywords: gcd
zbMATH Keywords: half-gcd
zbMATH Keywords: algorithm
describes a project that uses: Mathemagix
MaRDI profile type: Publication
full work available at URL: j.jsc.2018.04.017
OpenAlex ID: W2625628003
cites work: Minors of Bezout matrices, subresultants and the parameterization of the degree of the polynomial greatest common divisor
cites work: Bezout matrices, subresultant polynomials and parameters
cites work: Q4091421
cites work: A new method for computing polynomial greatest common divisors and polynomial remainder sequences
cites work: Q4274079
cites work: Matrix computation of subresultant polynomial remainder sequences in integral domains
cites work: Q2701991
cites work: Faster sparse multivariate polynomial interpolation of straight-line programs
cites work: On computing the determinant in small parallel time using a small number of processors
cites work: Reduction of bivariate polynomials from convex-dense to dense, with application to factorizations
cites work: Fast fraction-free triangularization of Bézoutians with applications to sub-resultant chain computation
cites work: Fast solution of toeplitz systems of equations and computation of Padé approximants
cites work: On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors
cites work: On Euclid's Algorithm and the Theory of Subresultants
cites work: Q4331740
cites work: On fast multiplication of polynomials over arbitrary algebras
cites work: Q3139838
cites work: Subresultants and Reduced Polynomial Remainder Sequences
cites work: Algorithme de Bareiss, algorithme des sous-résultants
cites work: Optimizations of the subresultant algorithm
cites work: An elementary approach to subresultants theory.
cites work: On the factorization of polynomials in a finite number of steps
cites work: Effective procedures in field theory
cites work: Deterministic root finding over finite fields using Graeffe transforms
cites work: Eine Verallgemeinerung des Sturmschen Wurzelzählverfahrens
cites work: Division-free computation of subresultants using Bezout matrices
cites work: Q4766043
cites work: Fast separable factorization and applications
cites work: Euclid's Algorithm for Large Numbers
cites work: Cauchy index computation
cites work: Sylvester-Habicht sequences and fast Cauchy index computation
cites work: New structure theorem for subresultants
cites work: Q3698903
cites work: Fast computation of GCDs
cites work: Q4226968
cites work: Fast computation of continued fraction expansions.
cites work: Q4111092
cites work: Q3947116
cites work: The Computational Complexity of Continued Fractions
cites work: Modular SIMD arithmetic in M <scp>athemagix</scp>
cites work: Modern computer algebra
cites work: Subresultants revisited.
cites work: Q4953977
Wikidata QID: Q130002428
DOI: 10.1016/J.JSC.2018.04.017
description: scientific article; zbMATH DE number 6997084