QRGCD - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

SNAP

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

 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

 > $\mathrm{with}\left(\mathrm{SNAP}\right):$
 > $f≔\mathrm{expand}\left(\left(x-5\right)\left(x-\frac{1}{2}\right)\left(56{x}^{8}+83{x}^{7}+91{x}^{4}-92{x}^{2}+93x-91\right)\right)$
 ${f}{≔}{56}{}{{x}}^{{10}}{-}{225}{}{{x}}^{{9}}{+}{91}{}{{x}}^{{6}}{+}\frac{{271}}{{2}}{}{{x}}^{{4}}{+}{599}{}{{x}}^{{3}}{-}\frac{{1665}}{{2}}{}{{x}}^{{2}}{-}\frac{{633}}{{2}}{}{{x}}^{{8}}{-}\frac{{1001}}{{2}}{}{{x}}^{{5}}{+}{733}{}{x}{+}\frac{{415}}{{2}}{}{{x}}^{{7}}{-}\frac{{455}}{{2}}$ (1)
 > $g≔\mathrm{expand}\left(\left(x-5\right)\left(x-\frac{1}{2}\right)\left(32{x}^{8}-37{x}^{6}+93{x}^{5}+58{x}^{4}+90{x}^{2}+53\right)\right)$
 ${g}{≔}{32}{}{{x}}^{{10}}{+}{43}{}{{x}}^{{8}}{+}\frac{{593}}{{2}}{}{{x}}^{{7}}{-}{546}{}{{x}}^{{6}}{+}{235}{}{{x}}^{{4}}{+}{278}{}{{x}}^{{2}}{-}{176}{}{{x}}^{{9}}{-}\frac{{173}}{{2}}{}{{x}}^{{5}}{-}{495}{}{{x}}^{{3}}{-}\frac{{583}}{{2}}{}{x}{+}\frac{{265}}{{2}}$ (2)
 > $\mathrm{eps}≔1.0{10}^{-4}$
 ${\mathrm{eps}}{≔}{0.0001000000000}$ (3)
 > $u,v,d≔\mathrm{QRGCD}\left(f,g,x,\mathrm{eps}\right)$
 ${u}{,}{v}{,}{d}{≔}{-}{0.00239210066773748}{+}{0.000685923025428412}{}{{x}}^{{7}}{-}{4.53097031258087}{×}{{10}}^{{-6}}{}{{x}}^{{6}}{-}{0.00164801014632734}{}{{x}}^{{5}}{+}{0.00111190210893585}{}{{x}}^{{4}}{+}{0.00232049175102826}{}{{x}}^{{3}}{-}{0.000814821101997568}{}{{x}}^{{2}}{-}{0.00159767495032094}{}{x}{,}{-}{0.000797538808884249}{-}{0.00120036529451165}{}{{x}}^{{7}}{-}{0.00177118364917771}{}{{x}}^{{6}}{+}{0.00150784758762038}{}{{x}}^{{5}}{+}{0.00376932816808507}{}{{x}}^{{4}}{+}{0.000171163088689716}{}{{x}}^{{3}}{-}{0.00139357959466411}{}{{x}}^{{2}}{+}{0.00145428191862992}{}{x}{,}{-}{0.964763821204430}{}{x}{+}{0.438529009807885}{+}{0.175411603893669}{}{{x}}^{{2}}$ (4)
 > $\mathrm{evalb}\left(\mathrm{evalf}\left(\mathrm{norm}\left(\mathrm{expand}\left(uf+vg-d\right),2\right)\right)<\mathrm{evalf}\left(\mathrm{max}\left(\mathrm{norm}\left(f,2\right),\mathrm{norm}\left(g,2\right),\mathrm{norm}\left(u,2\right),\mathrm{norm}\left(v,2\right),\mathrm{norm}\left(d,2\right)\right)\right)\mathrm{eps}\right)$
 ${\mathrm{true}}$ (5)
 > $\mathrm{f1}≔\mathrm{Quotient}\left(f,d,x\right)$
 ${\mathrm{f1}}{≔}{319.249118969040}{}{{x}}^{{8}}{+}{473.172800945553}{}{{x}}^{{7}}{-}{2.81222933045108}{×}{{10}}^{{-6}}{}{{x}}^{{6}}{-}{0.0000147072040345022}{}{{x}}^{{5}}{+}{518.779744465642}{}{{x}}^{{4}}{-}{0.000370080042164914}{}{{x}}^{{3}}{-}{524.482546459755}{}{{x}}^{{2}}{+}{530.172317845435}{}{x}{-}{518.826092219543}$ (6)
 > $\mathrm{evalb}\left(\mathrm{evalf}\left(\mathrm{norm}\left(\mathrm{expand}\left(f-\mathrm{f1}d\right),2\right)\right)<\mathrm{evalf}\left(\mathrm{norm}\left(f,2\right)\right)\mathrm{eps}\right)$
 ${\mathrm{true}}$ (7)
 > $\mathrm{g1}≔\mathrm{Quotient}\left(g,d,x\right)$
 ${\mathrm{g1}}{≔}{182.428067982309}{}{{x}}^{{8}}{-}{2.19177590934416}{×}{{10}}^{{-7}}{}{{x}}^{{7}}{-}{210.932454886683}{}{{x}}^{{6}}{+}{530.181566323192}{}{{x}}^{{5}}{+}{330.650841497779}{}{{x}}^{{4}}{-}{0.000159454935234903}{}{{x}}^{{3}}{+}{513.078143359541}{}{{x}}^{{2}}{-}{0.00399010296101806}{}{x}{+}{302.126536415563}$ (8)
 > $\mathrm{evalb}\left(\mathrm{evalf}\left(\mathrm{norm}\left(\mathrm{expand}\left(g-\mathrm{g1}d\right),2\right)\right)<\mathrm{evalf}\left(\mathrm{norm}\left(g,2\right)\right)\mathrm{eps}\right)$
 ${\mathrm{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.