Re: GCD of multivariate polynomials

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

Date: Tue, 30 Nov 2004 17:12:25 GMT

Christopher Creutzig wrote:

> Gagan Raj Gupta wrote:
>
>> Yes, I am looking for writing a program for computing the GCD of two
>> multivariate polynomials in a fast and efficient way.
>> What are the kind of data-structures that need to be used for this
>> problem?
>
>
> You should look into the required algorithms first. Multivariate
> polynomials do not form a Euclidean domain, so you don't have division
> with remainder (in the sense required by the Euclidean algorithm) and
> can't use the same methods as for univariate polynomials.
>
> regards,
> Christopher Creutzig

Mr. Gupta:
   You have already been given several suggestions for books to look at,
or key names for the WWW. You are apparently at IIT Delhi, studying
computer science, so you should have access to a library as well as
professors of mathematics and computer science. You should use the
resources at your disposal properly, instead of asking other people
far away to do your homework for you.
  In fact, somewhat contrary to Mr. Creutzig's comment, at least
one free, open-source program with many GCD algorithms
in several cases uses exactly the same methods for univariate polynomials
as for multivariate polynomials, (though not all univariate methods
work for multivariate).

When you have done some of the homework assigned to you yourself, and
understand the problem, you are welcome to ask pertinent questions
here. Your questions suggest you have only the vaguest idea of what GCD means.
What, for example is "kernel extraction" and what do you mean by the "quality"
of the GCD?

RJF

Relevant Pages

  • Re: GCD of multivariate polynomials
    ... I am looking for writing a program for computing the GCD of two ... multivariate polynomials in a fast and efficient way. ... >is necessary to simplify ratios of polynomials to simplest form. ...
    (sci.math.symbolic)
  • 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: 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)