QRGCD - Maple Help

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.00239210066773749+0.000685923025428402x74.53097031259547×10−6x60.00164801014632735x5+0.00111190210893584x4+0.00232049175102822x30.000814821101997623x20.00159767495032097x,0.0007975388088842760.00120036529451162x70.00177118364917765x6+0.00150784758762043x5+0.00376932816808507x4+0.000171163088689703x30.00139357959466412x2+0.00145428191862992x,0.964763821204428x+0.438529009807886+0.175411603893664x2

(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.249118969049x8+473.172800945610x72.81194552442132×10−6x60.0000147057859844261x5+518.779744472746x40.000370044520443826x3524.482546282163x2+530.172318733405x518.826087779702

(6)

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

true

(7)

g1Quotientg&comma;d&comma;x

g1182.428067982314x82.19151851293330×10−7x7210.932454886560x6+530.181566323818x5+330.650841500917x40.000159439241270405x3+513.078143438022x20.00398971055377326x+302.126538377605

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