GCDHEU: Heuristic polynomial GCD algorithm based on integer GCD computation
type: Item
instance of: scholarly article
title: GCDHEU: Heuristic polynomial GCD algorithm based on integer GCD computation
zbMATH Open document ID: 0679.12013
DOI: 10.1016/S0747-7171(89)80004-5
author: Bruce W. Char
author: Keith O. Geddes
author: Gaston H. Gonnet
published in: Journal of Symbolic Computation
publication date: 1989-01-01T00:00:00Z
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.
Mathematics Subject Classification ID: 12D05
Mathematics Subject Classification ID: 11R09
Mathematics Subject Classification ID: 12-04
Mathematics Subject Classification ID: 68W30
zbMATH DE Number: 4112727
zbMATH Keywords: heuristic methods
zbMATH Keywords: height of a polynomial
zbMATH Keywords: G.C.D. of multivariate polynomials
describes a project that uses: Maple
MaRDI profile type: Publication
cites work: Q4091421
cites work: On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors
cites work: The Subresultant PRS Algorithm
cites work: Q3707405
cites work: Subresultants and Reduced Polynomial Remainder Sequences
cites work: Q3740227
cites work: Q4192968
cites work: Q5585020
cites work: Q3963114
cites work: The EEZ-GCD algorithm
cites work: Q3851616
full work available at URL: s0747-7171(89)80004-5
OpenAlex ID: W2077853647
description: scientific article; zbMATH DE number 4112727