GCD - Maple Help

PolynomialTools[Approximate]

 GCD
 compute approximate multivariate GCD

 Calling Sequence GCD(F, G, vars) GCD(F, G, vars, options)

Parameters

 F - polynom({numeric,complex(numeric)}) G - polynom({numeric,complex(numeric)}) vars - a set or list of variables

Options

 • cofactors
 if provided, the command returns $d,u,v$ where d is the gcd, and u and v are the cofactors such that $\frac{f}{u}=d$ and $\frac{g}{v}=d$.
 • noexact
 if provided, exact gcd computation will not be attempted
 • optimize
 if given then a post-processing step is done on the output, using Optimization[NLPSolve] to return an approximate gcd with smaller backward error. Optionally, it can be given as optimize=list with a list of extra options to be passed to optimization.

Description

 • After some basic preprocessing to handle exact cases, the numerical gcd of F and G is computed by projecting to the univariate case to determine the degree of the approximate GCD, then the GCD cofactors are computed from the low rank approximation of the generalized SylvesterMatrix. Finally, the GCD is computed with a least-squares polynomial division.
 • This command will work on univariate polynomials, but there are several other options for the univariate case in the SNAP package.

Examples

 > $\mathrm{with}\left(\mathrm{PolynomialTools}:-\mathrm{Approximate}\right):$
 > $\mathrm{infolevel}\left[\mathrm{PolynomialTools}\right]≔1$
 ${{\mathrm{infolevel}}}_{{\mathrm{PolynomialTools}}}{≔}{1}$ (1)
 > $d≔\mathrm{sqrt}\left(2.0\right)\left({x}^{2}+{y}^{2}-1\right)$
 ${d}{≔}{1.414213562}{}{{x}}^{{2}}{+}{1.414213562}{}{{y}}^{{2}}{-}{1.414213562}$ (2)
 > $F≔\mathrm{sort}\left(\mathrm{expand}\left(d\left({x}^{3}-{y}^{3}+1\right)\right),\left[x,y\right]\right)$
 ${F}{≔}{1.414213562}{}{{x}}^{{5}}{+}{1.414213562}{}{{x}}^{{3}}{}{{y}}^{{2}}{-}{1.414213562}{}{{x}}^{{2}}{}{{y}}^{{3}}{-}{1.414213562}{}{{y}}^{{5}}{-}{1.414213562}{}{{x}}^{{3}}{+}{1.414213562}{}{{y}}^{{3}}{+}{1.414213562}{}{{x}}^{{2}}{+}{1.414213562}{}{{y}}^{{2}}{-}{1.414213562}$ (3)
 > $G≔\mathrm{sort}\left(\mathrm{expand}\left(d\left({x}^{2}-{y}^{3}+1\right)\right),\left[x,y\right]\right)$
 ${G}{≔}{-}{1.414213562}{}{{x}}^{{2}}{}{{y}}^{{3}}{-}{1.414213562}{}{{y}}^{{5}}{+}{1.414213562}{}{{x}}^{{4}}{+}{1.414213562}{}{{x}}^{{2}}{}{{y}}^{{2}}{+}{1.414213562}{}{{y}}^{{3}}{+}{1.414213562}{}{{y}}^{{2}}{-}{1.414213562}$ (4)
 > $\mathrm{ad_8}≔\mathrm{GCD}\left(\mathrm{expand}\left(F+{10}^{-8}xy\right),\mathrm{expand}\left(G+{10}^{-8}{x}^{2}y\right),\left[x,y\right]\right)$
 GCD:   approximate GCD inputs of total degrees 5 and 5 in [x, y] GCD:   approximate GCD determined with an error of 7.484964e-10
 ${\mathrm{ad_8}}{≔}{0.569494797046587}{+}{3.40007756198411}{×}{{10}}^{{-10}}{}{x}{-}{1.02787952298720}{×}{{10}}^{{-9}}{}{y}{-}{0.569494797402477}{}{{x}}^{{2}}{-}{1.49456595411036}{×}{{10}}^{{-10}}{}{x}{}{y}{-}{0.569494797883116}{}{{y}}^{{2}}$ (5)
 > $\mathrm{ad_8}≔\mathrm{sort}\left(\mathrm{tcoeff}\left(d\right)\mathrm{fnormal}\left(\frac{\mathrm{expand}\left(\mathrm{ad_8}\right)}{\mathrm{tcoeff}\left(\mathrm{ad_8}\right)}\right),\left[x,y\right]\right)$
 ${\mathrm{ad_8}}{≔}{1.414213563}{}{{x}}^{{2}}{+}{1.414213563}{}{{y}}^{{2}}{-}{1.414213562}$ (6)
 > $\mathrm{ilog10}\left(\frac{\mathrm{norm}\left(\mathrm{expand}\left(d-\mathrm{ad_8}\right),2\right)}{\mathrm{norm}\left(d,2\right)}\right)$
 ${-10}$ (7)
 > $\mathrm{ad_4}≔\mathrm{GCD}\left(\mathrm{expand}\left(F+{10}^{-5}\mathrm{randpoly}\left(\left\{x,y\right\},\mathrm{degree}=2\right)\right),\mathrm{expand}\left(G+{10}^{-5}\mathrm{randpoly}\left(\left\{x,y\right\},\mathrm{degree}=2\right)\right),\left[x,y\right]\right)$
 GCD:   approximate GCD inputs of total degrees 5 and 5 in [x, y] GCD:   approximate GCD determined with an error of 1.258109e-04
 ${\mathrm{ad_4}}{≔}{0.569558529000008}{-}{0.0000570803626101716}{}{x}{-}{0.0000202745885675310}{}{y}{-}{0.569452652923380}{}{{x}}^{{2}}{-}{0.0000375128607617162}{}{x}{}{y}{-}{0.569477701446847}{}{{y}}^{{2}}$ (8)
 > $\mathrm{ad_4}≔\mathrm{sort}\left(\mathrm{tcoeff}\left(d\right)\mathrm{fnormal}\left(\frac{\mathrm{expand}\left(\mathrm{ad_4}\right)}{\mathrm{tcoeff}\left(\mathrm{ad_4}\right)}\right),\left[x,y\right]\right)$
 ${\mathrm{ad_4}}{≔}{1.413950672}{}{{x}}^{{2}}{+}{0.00009314441579}{}{x}{}{y}{+}{1.414012867}{}{{y}}^{{2}}{+}{0.0001417305137}{}{x}{+}{0.00005034179397}{}{y}{-}{1.414213562}$ (9)
 > $\mathrm{ilog10}\left(\frac{\mathrm{norm}\left(\mathrm{expand}\left(d-\mathrm{ad_4}\right),2\right)}{\mathrm{norm}\left(d,2\right)}\right)$
 ${-4}$ (10)

References

 Gao, S.; Kaltofen, E.; May, J.; Yang, Z.; and Zhi, L. "Approximate factorization of multivariate polynomials via differential equations." Proceedings of the 2004 International Symposium on Symbolic and Algebraic Computation (ISSAC 2004),  pp. 167-174. Ed. J. Guitierrez. ACM Press, 2004.

Compatibility

 • The PolynomialTools:-Approximate:-GCD command was introduced in Maple 2021.