QRGCD - Maple Help

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.00239210066773749}{+}{0.000685923025428402}{}{{x}}^{{7}}{-}{4.53097031259547}{×}{{10}}^{{-6}}{}{{x}}^{{6}}{-}{0.00164801014632735}{}{{x}}^{{5}}{+}{0.00111190210893584}{}{{x}}^{{4}}{+}{0.00232049175102822}{}{{x}}^{{3}}{-}{0.000814821101997623}{}{{x}}^{{2}}{-}{0.00159767495032097}{}{x}{,}{-}{0.000797538808884276}{-}{0.00120036529451162}{}{{x}}^{{7}}{-}{0.00177118364917765}{}{{x}}^{{6}}{+}{0.00150784758762043}{}{{x}}^{{5}}{+}{0.00376932816808507}{}{{x}}^{{4}}{+}{0.000171163088689703}{}{{x}}^{{3}}{-}{0.00139357959466412}{}{{x}}^{{2}}{+}{0.00145428191862992}{}{x}{,}{-}{0.964763821204428}{}{x}{+}{0.438529009807886}{+}{0.175411603893664}{}{{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.249118969049}{}{{x}}^{{8}}{+}{473.172800945610}{}{{x}}^{{7}}{-}{2.81194552442132}{×}{{10}}^{{-6}}{}{{x}}^{{6}}{-}{0.0000147057859844261}{}{{x}}^{{5}}{+}{518.779744472746}{}{{x}}^{{4}}{-}{0.000370044520443826}{}{{x}}^{{3}}{-}{524.482546282163}{}{{x}}^{{2}}{+}{530.172318733405}{}{x}{-}{518.826087779702}$ (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.428067982314}{}{{x}}^{{8}}{-}{2.19151851293330}{×}{{10}}^{{-7}}{}{{x}}^{{7}}{-}{210.932454886560}{}{{x}}^{{6}}{+}{530.181566323818}{}{{x}}^{{5}}{+}{330.650841500917}{}{{x}}^{{4}}{-}{0.000159439241270405}{}{{x}}^{{3}}{+}{513.078143438022}{}{{x}}^{{2}}{-}{0.00398971055377326}{}{x}{+}{302.126538377605}$ (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.