Certified approximate univariate GCDs
type: Item
instance of: scholarly article
title: Certified approximate univariate GCDs
zbMATH Open document ID: 0891.65015
DOI: 10.1016/S0022-4049(97)00013-3
author: Ioannis Z. Emiris
author: Henri Lombardi
author: André Galligo
published in: Journal of Pure and Applied Algebra
publication date: 1998-07-19T00:00:00Z
review text: The paper deals with computing the approximate greatest common divisor (GCD) of two univariate polynomials given with limited accuracy. The authors provide a counterexample to the direct approach which relies only on the Sylvester matrix singular values and on the extended Euclidean algorithm. It is concluded that Euclid's algorithm is unable to find the maximum-degree GCD polynomial within some guaranteed error. The authors use a direct algebraic approach to prove a gap theorem on the singular values of the subresultant matrices that guarantees the degree for the approximate GCD.
Mathematics Subject Classification ID: 65D20
Mathematics Subject Classification ID: 12Y05
Mathematics Subject Classification ID: 26C10
Mathematics Subject Classification ID: 15A18
Mathematics Subject Classification ID: 65Y20
Mathematics Subject Classification ID: 68W30
zbMATH DE Number: 1025698
zbMATH Keywords: greatest common divisor
zbMATH Keywords: polynomials
zbMATH Keywords: Sylvester matrix singular values
zbMATH Keywords: extended Euclidean algorithm
reviewed by: Emil Minchev
MaRDI profile type: Publication
cites work: Products of polynomials and a priori estimates for coefficients in polynomial decompositions: A sharp result
cites work: Products of polynomials in many variables
cites work: On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors
cites work: Subresultants and Reduced Polynomial Remainder Sequences
cites work: Q4227296
cites work: Efficient incremental algorithms for the sparse resultant and the mixed volume
cites work: Q4717942
cites work: On the numerical condition of polynomials in Bernstein form
cites work: Q3263792
cites work: Q3359644
cites work: Q4391225
cites work: Zur inhomogenen Eliminationstheorie
cites work: Detection and validation of clusters of polynomial zeros
cites work: A matrix pencil based numerical method for the computation of the GCD of polynomials
cites work: Q4227320
cites work: Résolution des systèmes d'équations algébriques
cites work: Parallel robots.
cites work: An Inequality About Factors of Polynomials
cites work: Approximate GCD and its application to ill-conditioned algebraic equations
cites work: On application of some recent techniques of the design of algebraic algorithms to the sequential and parallel evaluation of the roots of a polynomial and to some other numerical problems
cites work: Quasi-gcd computations
cites work: Best linear common divisors for approximate degree reduction
cites work: Q4284599
full work available at URL: s0022-4049(97)00013-3
OpenAlex ID: W2061311874
description: scientific article; zbMATH DE number 1025698