GCDHEU: Heuristic polynomial GCD algorithm based on integer GCD computation (Q1124635): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set OpenAlex properties. |
||
(3 intermediate revisions by 3 users not shown) | |||
Property / describes a project that uses | |||
Property / describes a project that uses: Maple / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4091421 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Subresultant PRS Algorithm / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3707405 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Subresultants and Reduced Polynomial Remainder Sequences / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3740227 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4192968 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5585020 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3963114 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The EEZ-GCD algorithm / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3851616 / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/s0747-7171(89)80004-5 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2077853647 / rank | |||
Normal rank |
Latest revision as of 11:11, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | GCDHEU: Heuristic polynomial GCD algorithm based on integer GCD computation |
scientific article |
Statements
GCDHEU: Heuristic polynomial GCD algorithm based on integer GCD computation (English)
0 references
1989
0 references
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.
0 references
heuristic methods
0 references
height of a polynomial
0 references
G.C.D. of multivariate polynomials
0 references