GCDHEU: Heuristic polynomial GCD algorithm based on integer GCD computation

DOI10.1016/S0747-7171(89)80004-5MaRDI QIDQ1124635zbMATH OpenOpenAlexFDO

Authors Bruce W. Char, Keith O. Geddes, Gaston H. Gonnet

Publication date 1989

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

Full work available at URL https://doi.org/10.1016/s0747-7171(89)80004-5

zbMATH Keywords

G.C.D. of multivariate polynomialsheight of a polynomialheuristic methods

Mathematics Subject Classification ID

Polynomials (irreducibility, etc.) (11R09) Software, source code, etc. for problems pertaining to field theory (12-04) Polynomials in real and complex fields: factorization (12D05) Symbolic computation and algebraic computation (68W30)

Review text

Let a and b be two primitive univariate polynomials, and let g be their greatest common divisor. The height of a polynomial is the maximum of the absolute values of its coefficients: let n be greater than twice the heights of a,b, or any of their factors, and let \(h=(a(n),b(n))\). Expand h n-adically as \(h_ 0+h_ 1n+...+h_ kn^ k\) where \(-n/2<h_ i\leq n/2\); then if \(h(x)=h_ 0+h_ 1x+...+h_ kx^ k\) divides a and b it is in fact g. It is possible for h(x) to be Lg(x) where L is some integer greater than 1; if an increasing sequence of values of n is used then the probability of h(x) being g(x) increases to unity. The method can be extended to find the G.C.D. of multivariate polynomials.

Recommendations

• scientific article; zbMATH DE number 3974286
• scientific article; zbMATH DE number 17841
• Fast computation of GCDs
• scientific article; zbMATH DE number 3984564
• Probabilistic computation of integer polynomial GCDs

Cites work

• scientific article; zbMATH DE number 3936514 (Why is no real title available?)
• scientific article; zbMATH DE number 3974286 (Why is no real title available?)
• scientific article; zbMATH DE number 3651744 (Why is no real title available?)
• scientific article; zbMATH DE number 3785018 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3631929 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors
• Subresultants and Reduced Polynomial Remainder Sequences
• The EEZ-GCD algorithm
• The Subresultant PRS Algorithm

Cited in

(9)

• Three new algorithms for multivariate polynomial GCD
• GCDHEU
• On degrees of modular common divisors and the big prime gcd algorithm
• A fast parallel sparse polynomial GCD algorithm
• Nikolai Ivanovich Lobachevskii (on the bicentenary of his birth)
• Estimating the greatest common divisor of the value of two polynomials
• In honour of Keith Geddes on his 60th birthday
• Gcd of multivariate polynomials via Newton polytopes
• A new sparse polynomial GCD by separating terms

Describes a project that uses

Uses Software

• Maple

This page was built for publication: GCDHEU: Heuristic polynomial GCD algorithm based on integer GCD computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1124635)