Approximate polynomial GCD: small degree and small height perturbations

DOI10.1016/j.jsc.2010.04.001zbMath1248.11106OpenAlexW2037437408MaRDI QIDQ979147

Joachim von zur Gathen, Maurice Mignotte, Igor E. Shparlinski

Publication date: 25 June 2010

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jsc.2010.04.001

zbMATH Keywords

Euclidean algorithmgcdapproximate computation

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Polynomials in number theory (11C08) Randomized algorithms (68W20) Numerical approximation and computational geometry (primarily algorithms) (65D99)

Related Items

Approximate GCD of several univariate polynomials with small degree perturbations, Approximate polynomial GCD over integers, Overdetermined Weierstrass iteration and the nearest consistent system, Toward the best algorithm for approximate GCD of univariate polynomials, On the greatest common divisor of shifted sets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Quasi-gcd computations
• On approximate GCDs of univariate polynomials
• An algorithm for computing certified approximate GCD of \(n\) univariate polynomials
• Certified approximate univariate GCDs
• Computation of approximate polynomial GCDs and an extension
• Approximate greatest common divisor of many polynomials, generalised resultants, and strength of approximation
• Approximate Polynomial gcd: Small Degree and Small Height Perturbations