GcdFreeBasis - Maple Help

PolynomialTools

 GcdFreeBasis
 compute a gcd free basis of a set or list of polynomials

 Calling Sequence GcdFreeBasis(S)

Parameters

 S - set or list of polynomials

Description

 • The GcdFreeBasis command uses repeated gcd computations to compute a gcd free basis B of the polynomials in S. B satisfies the following properties.
 – Each polynomial in S can be written as a constant times a product of polynomials from B.
 – The polynomials in B are pairwise coprime, that is, their gcd is constant.
 – With respect to cardinality, B is minimal with these properties. (This is equivalent to saying that B can be computed using gcds and divisions only, but not factorization.)
 • The gcd free basis is unique up to ordering and multiplication of the basis elements by constants.
 • GcdFreeBasis can handle the same types of coefficients as the Maple function gcd.
 • If S is a set, then the output is a set as well. If S is a list, then the output is also a list. The ordering of the elements in the result is not determined in either case.
 • Zero polynomials and constants are ignored. In particular, for a constant const, GcdFreeBasis([const]) returns [ ]. The empty set or list is a valid input and is returned unchanged.
 • A polynomial $f$ is considered constant by GcdFreeBasis if $\mathrm{degree}\left(f\right)$ returns $0$.

Examples

 > $\mathrm{with}\left(\mathrm{PolynomialTools}\right):$
 > $\mathrm{GcdFreeBasis}\left(\left[abcd,abce,abde\right]\right)$
 $\left[{c}{,}{d}{,}{e}{,}{a}{}{b}\right]$ (1)
 > $\mathrm{GcdFreeBasis}\left(\left\{{x}^{6}-1,{x}^{10}-1,{x}^{15}-1\right\}\right)$
 $\left\{{x}{-}{1}{,}{x}{+}{1}{,}{{x}}^{{2}}{-}{x}{+}{1}{,}{{x}}^{{2}}{+}{x}{+}{1}{,}{{x}}^{{4}}{-}{{x}}^{{3}}{+}{{x}}^{{2}}{-}{x}{+}{1}{,}{{x}}^{{4}}{+}{{x}}^{{3}}{+}{{x}}^{{2}}{+}{x}{+}{1}{,}{{x}}^{{8}}{-}{{x}}^{{7}}{+}{{x}}^{{5}}{-}{{x}}^{{4}}{+}{{x}}^{{3}}{-}{x}{+}{1}\right\}$ (2)

References

 Bach, Eric.; Driscoll, James.; and Shallit, Jeffrey. "Factor Refinement." Journal of Algorithms Vol. 15(2), (1993): 199-222.