GCDHEU: Heuristic polynomial GCD algorithm based on integer GCD computation (Q1124635): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
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 |
Revision as of 10:26, 20 June 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