QRGCD - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.
Our website is currently undergoing maintenance, which may result in occasional errors while browsing. We apologize for any inconvenience this may cause and are working swiftly to restore full functionality. Thank you for your patience.

Online Help

All Products    Maple    MapleSim


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.53097031258087×10−6x60.00164801014632734x5+0.00111190210893585x4+0.00232049175102826x30.000814821101997568x20.00159767495032094x,0.0007975388088842490.00120036529451165x70.00177118364917771x6+0.00150784758762038x5+0.00376932816808507x4+0.000171163088689716x30.00139357959466411x2+0.00145428191862992x,0.964763821204430x+0.438529009807885+0.175411603893669x2

(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.249118969040x8+473.172800945553x72.81222933045108×10−6x60.0000147072040345022x5+518.779744465642x40.000370080042164914x3524.482546459755x2+530.172317845435x518.826092219543

(6)

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

true

(7)

g1Quotientg&comma;d&comma;x

g1182.428067982309x82.19177590934416×10−7x7210.932454886683x6+530.181566323192x5+330.650841497779x40.000159454935234903x3+513.078143359541x20.00399010296101806x+302.126536415563

(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]

 


Download Help Document