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

Online Help

All Products    Maple    MapleSim


PolynomialTools[Approximate]

  

GCD

  

compute approximate multivariate GCD

 

Calling Sequence

Parameters

Options

Description

Examples

References

Compatibility

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 fu=d and gv=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

withPolynomialTools:-Approximate:

infolevelPolynomialTools1

infolevelPolynomialTools1

(1)

d2.0x2+y21

d1.414213562x2+1.414213562y21.414213562

(2)

Fsortexpanddx3y3+1,x,y

F1.414213562x5+1.414213562x3y21.414213562x2y31.414213562y51.414213562x3+1.414213562y3+1.414213562x2+1.414213562y21.414213562

(3)

Gsortexpanddx2y3+1,x,y

G1.414213562x2y31.414213562y5+1.414213562x4+1.414213562x2y2+1.414213562y3+1.414213562y21.414213562

(4)

ad_8GCDexpandF+108xy,expandG+108x2y,x,y

GCD:   approximate GCD inputs of total degrees 5 and 5 in [x, y]
GCD:   approximate GCD determined with an error of 7.484964e-10

ad_80.569494797046587+3.40008238745826×10−10x1.02787949443617×10−9y0.569494797402477x21.49456632732006×10−10xy0.569494797883116y2

(5)

ad_8sorttcoeffdfnormalexpandad_8tcoeffad_8,x,y

ad_81.414213563x2+1.414213563y21.414213562

(6)

ilog10normexpanddad_8,2normd,2

−10

(7)

ad_4GCDexpandF+105randpolyx,y,degree=2,expandG+105randpolyx,y,degree=2,x,y

GCD:   approximate GCD inputs of total degrees 5 and 5 in [x, y]
GCD:   approximate GCD determined with an error of 1.258109e-04

ad_40.5695585290000080.0000570803626106371x0.0000202745885674440y0.569452652923380x20.0000375128607616705xy0.569477701446848y2

(8)

ad_4sorttcoeffdfnormalexpandad_4tcoeffad_4,x,y

ad_41.413950672x2+0.00009314441579xy+1.414012867y2+0.0001417305137x+0.00005034179397y1.414213562

(9)

ilog10normexpanddad_4,2normd,2

−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.

• 

For more information on Maple 2021 changes, see Updates in Maple 2021.

See Also

gcd

SNAP

SylvesterMatrix