Re: High Precision Approximate GCD

From: Z. Zeng (zzeng_at_neiu.edu)
Date: 07/23/04 

Date: Fri, 23 Jul 2004 16:04:52 GMT

EpsilonGCD and QuasiGCD are probably the first packages available. By
today's standared, they
work for low degree polynomials only and may fail often. QRGCD (in SNAP,
Maple 9) is much more
robust and accurate.

Here is a comparison among EpsilongGCD, QRGCD and UvGCD on a simple example:

Let

p = (x-1)^i*(x-2)^j*(x-3)^k*(x-4)^l
q = p'

GCD(p,q) = (x-1)^(i-1) * (x-2)^(j-1) * (x-3)^(k-1) * (x-4)^(l-1)

For different sets of [i,j,k,l], the following table lists the error in
computed approximate GCD's
using hardware precision (16 digits)

  [i,j,k,l] EpsilonGCD QRGCD UvGCD*
------------------------------------------------------
   2,1,1,0 Fail 1e-13 7e-16
   3,2,1,0 Fail 1e-12 2e-14
   4,3,2,1 Fail 2e-07 5e-14
   5,3,2,1 Fail Fail 5e-13
   9,6,4,2 Fail Fail 4e-12
20,14,10,5 Fail Fail 2e-12
80,60,40,20 Fail Fail 4e-11

QuasiGCD shows similar results.

(*) UvGCD is reported in "The approximate GCD of inexact polynomials. Part
I: a
univariate algorithm", Z. Zeng

Zhonggang Zeng

"Thomas Richard" <t.richard@scientific.de> wrote in message
news:40ffef0d.268228812@news.individual.de...
> muhammad.yaqoob@imperial.ac.uk (Moeen) wrote:
>
> > I have two quartic numerical polynomials of the form
> >
> > a4.x^4 + a3.x^3 + a2.x^2 + a0 = 0
> > [...]
> > So, in essence, i am trying to find out the gcd (upto 7th or 8th
> > decimal place) of two numeric quartic polynomials whose coefficients
> > may be perturbed. I have tried a few methods of finding gcd of numeric
> > polynomials but they fail to provide such higher precision. Instead,
>
> I'm not familiar with that topic, but in case you have Maple 8 or newer,
> I guess the SNAP package could help you. There's a paper on it:
>
> Jeannerod, C-P. and Labahn, G. "The SNAP package for numerical
> polynomial arithmetic in Maple" Computer Science Technical Report,
> University of Waterloo (2002).
>
> The package has commands like EpsilonGCD and QuasiGCD and others.
>
> --
> Thomas Richard
> Maple Support
> Scientific Computers GmbH
> http://www.scientific.de

Relevant Pages

  • Re: commutative polynomial ideals in Mathematica and Maple
    ... > Maple 10 added some new functionality for working with commutative ... > polynomial ideals. ... One gets minimal univariate polynomials in each variable. ...
    (sci.math.symbolic)
  • Re: Polynomial package
    ... I am trying to use the polynomial package, for polynomials with large ... coefficients, but I am running into problems (the package I am using ... The command omits terms where the coefficient is 0 and omits the ...
    (comp.text.tex)
  • Re: Make the denominator rational
    ... But by Newton's theorem these polynomials ... are the rational integer coefficients of the monic ... How to do it with Maple for example? ... as we await bird flu shots and fight a real cold war. ...
    (sci.math)
  • Re: Logarithm related identities
    ... Since there are tons of these that can be made: ... All rational functions in x (fractions of polynomials) can be written ... I copied the first expression into Maple: ...
    (sci.math.research)
  • Re: How to find the asymptotic expansion of generalized Laguerre
    ... generalized Laguerre polynomial, with respect to x. ... It is strange that Maple does not recognize this. ... It is strange that Mathematica does not consider what they call ... > orthogonal polynomials. ...
    (sci.math.symbolic)
Loading