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&plus;83x7&plus;91x492x2&plus;93x91

f:=56x10225x9&plus;91x6&plus;2712x4&plus;599x316652x26332x810012x5&plus;733x&plus;4152x74552

(1)

gexpandx5x1232x837x6&plus;93x5&plus;58x4&plus;90x2&plus;53

g:=32x10&plus;43x8&plus;5932x7546x6&plus;235x4&plus;278x2176x91732x5495x35832x&plus;2652

(2)

eps1.0104

eps:=0.0001000000000

(3)

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

u&comma;v&comma;d:=0.00239210066773749&plus;0.000685923025428400x70.00000453097031259658x60.00164801014632734x5&plus;0.00111190210893584x4&plus;0.00232049175102822x30.000814821101997621x20.00159767495032098x&comma;0.0007975388088842770.00120036529451163x70.00177118364917765x6&plus;0.00150784758762044x5&plus;0.00376932816808507x4&plus;0.000171163088689710x30.00139357959466411x2&plus;0.00145428191862991x&comma;0.964763821204429x&plus;0.438529009807885&plus;0.175411603893666x2

(4)

evalbevalfnormexpanduf&plus;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

f1:=319.249118969045x8&plus;473.172800945584x70.00000281207443126255x60.0000147064292235401x5&plus;518.779744469523x40.000370060635746702x3524.482546362732x2&plus;530.172318330555x518.826089793950

(6)

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

true

(7)

g1Quotientg&comma;d&comma;x

g1:=182.428067982311x82.1916336681848310-7x7210.932454886615x6&plus;530.181566323540x5&plus;330.650841499522x40.000159446217375722x3&plus;513.078143403138x20.00398988497569566x&plus;302.126537505494

(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

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam