Re: GCD of multivariate polynomials

From: Richard Fateman (fateman_at_cs.berkeley.edu)
Date: 11/05/04 

Date: Fri, 05 Nov 2004 16:04:21 GMT

Mitch Harris wrote:
> Gagan Raj Gupta wrote:
>
>> I wish to know if there is a way to compute the GCD of 2 multivariate
>> polynomials.

1. Yes, there is a way.
Now for the questions you did NOT ask..
2. Just about any computer algebra system has such a capability, which
is necessary to simplify ratios of polynomials to simplest form.
3. There are public open-source programs with this capability.
4. It is a well-studied problem, and you can find simple programs
or far more elaborate programs that are efficient for large cases.
5. The names Reduced, Subresultant, Modular, EZGCD, Heuristic, Sparse,
will be found if you Google for the subject.
6. If you are writing such a program, I recommend you NOT
start with an exponential time
procedure (Buchberger's algorithm) and hope that the special case
of GCD will come out faster. You can write such a program more
directly. Assuming you already know how to represent polynomials
in several variables over the integers, and can add, multiply, and
compute remainders, a decent GCD program, say subresultant, can
fit on half a page. A useful treatment can be found in Knuth's
Art of Computer programming Volume 2. I think that the 'details'
you find in Cox etal, and books on Groebner bases will not address the computational
task, but only the mathematical implications. If that is what
you want, fine.

RJF
>>
>> For eg, the gcd of abcd + abe+c^2d+ec+ecd+e^2 and
>> abgh+abk+abl+cgh+ck+cl is ab+c+e.
>>
>> I constructed this by doing (ab+c+e)(cd+e) and (ab+c+e)(gh+k).
>
>
> (I think you meant abgh+abk+cgh+egh+ck+ek)
>
> Yes, it's possible. As with (plain old) integers, factoring is -not-
> the most efficient method (in general) for computing the gcd.
>
> What does work is a more generalized Euclidean gcd algorithm (divide
> the "larger" by the "smaller", repeat with the remainder, stop when
> you get to 0, the remainder before you get 0 is the gcd).
>
> But larger and smaller are not so obvious here you have to order the
> variables (and so then also the terms). And there are other
> complications to deal with. For the details see any book
> on Groebner bases and Buchberger's algorithm (Cox, Little, O'Shea:
> Ideals, Varieties, and Algorithms is nice).
>

Relevant Pages

  • Re: euclidean algorithm over Q[i]
    ... Z, the Gaussian integers, may be what you remember seeing. ... written a pretty simplistic algorithm in java that carries out polynomial ... GCD, just using polynomial long division and the euclidean algorithm. ... GCD's of univariate polynomials over Q? ...
    (sci.math.symbolic)
  • Re: High Precision Approximate GCD
    ... gcd as a set of linear equations to be solved, ... values or when the polynomials are only _approximately_ equal to ... for the two polynomials, and using random leading coefficients as well, ... expanded forms of p and q had moved the roots around nearly as ...
    (sci.math.symbolic)
  • Re: euclidean algorithm over Q[i]
    ... apart from the final value for the gcd. ... Are you using the Euclidean algorithm to compute ... GCD's of univariate polynomials over Q? ... advantage to using 'pseudo division' to avoid large ...
    (sci.math.symbolic)
  • Re: A GCD question
    ... it's not much more difficult to find the GCD if two polynomials in a ... similiar way. ... Three New Algorithms for Multivariate Polynomial GCD ...
    (sci.math)
  • Re: High Precision Approximate GCD
    ... For given polynomial p and q, the degree of u; solve linear system ... Back to the GCD problem. ... Computing GCD is a two stage process. ... polynomials" that is now available at Math. ...
    (sci.math.symbolic)