SNAP - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Numerical Computations : SNAP Package : SNAP/QRGCD

SNAP

  

QRGCD

  

compute GCD for a pair of univariate numeric polynomials by using QR factoring

 

Calling Sequence

Parameters

Description

Examples

References

Calling Sequence

QRGCD(f, g, x, eps)

Parameters

f, g

-

univariate numeric polynomials

x

-

name; indeterminate for f and g

eps

-

type numeric and non-negative; stability parameter

Description

• 

The QRGCD(f, g, x, eps) function returns univariate numeric polynomials u,v,d such that d is an approximate-GCD for the input polynomials (f, g). (See [1] for the definition of an approximate-GCD.)

• 

With high probability, the output polynomials satisfy || u * f + v * g - d || < ||(f,g,u,v,d)|| * eps, || f - d * f1 || < ||f|| * eps, and || g - d * g1 || < ||g|| * eps, where the polynomials f1 and f2 are cofactors of f and g with respect to the divisor d.

• 

The output polynomials u and v satisfy deg(u) < deg(g) - deg(d) and deg(v) < deg(f) - deg(d).

Examples

withSNAP&colon;

fexpandx5x1256x8+83x7+91x492x2+93x91

f56x10225x9+91x6+2712x4+599x316652x26332x810012x5+733x+4152x74552

(1)

gexpandx5x1232x837x6+93x5+58x4+90x2+53

g32x10+43x8+5932x7546x6+235x4+278x2176x91732x5495x35832x+2652

(2)

eps1.0104

eps0.0001000000000

(3)

u,v,dQRGCDf&comma;g&comma;x&comma;eps

u,v,d0.00239210066773748+0.000685923025428412x74.5309703125822210−6x60.00164801014632734x5+0.00111190210893585x4+0.00232049175102825x30.000814821101997574x20.00159767495032095x,0.0007975388088842630.00120036529451166x70.00177118364917770x6+0.00150784758762039x5+0.00376932816808507x4+0.000171163088689721x30.00139357959466410x2+0.00145428191862992x,0.964763821204430x+0.438529009807885+0.175411603893670x2

(4)

evalbevalfnormexpanduf+vgd&comma;2<evalfmaxnormf&comma;2&comma;normg&comma;2&comma;normu&comma;2&comma;normv&comma;2&comma;normd&comma;2eps

true

(5)

f1Quotientf&comma;d&comma;x

f1319.249118969039x8+473.172800945542x72.8122890245758410−6x60.0000147075025067559x5+518.779744464146x40.000370087521006449x3524.482546497146x2+530.172317658475x518.826093154336

(6)

evalbevalfnormexpandff1d&comma;2<evalfnormf&comma;2eps

true

(7)

g1Quotientg&comma;d&comma;x

g1182.428067982308x82.1918349817542010−7x7210.932454886712x6+530.181566323042x5+330.650841497020x40.000159458726201784x3+513.078143340583x20.00399019775146472x+302.126535941609

(8)

evalbevalfnormexpandgg1d&comma;2<evalfnormg&comma;2eps

true

(9)

References

  

Corless, R. M.; Watt, S. M.; and Zhi, L. "QR Factoring to compute the GCD of Univariate Approximate Polynomials." IEEE Transactions on Signal Processing. Vol. 52(12), (2004): 3394-3402.

See Also

SNAP[DistanceToCommonDivisors]

SNAP[EpsilonGCD]

SNAP[QuasiGCD]