OreTools - Maple Programming Help

Home : Support : Online Help : Mathematics : Algebra : Skew Polynomials : OreTools : OreTools/GCDLCM

OreTools

 GCD
 compute greatest common right or left divisor (GCRD or GCLD) of Ore polynomials
 LCM
 compute least common left or right multiple (LCLM or LCRM) of Ore polynomials
 ExtendedGCD
 compute the GCRD or GCLD of two Ore polynomials and the last two members of the first or/and second co-sequences

 Calling Sequence GCD['right'](Poly1, Poly2, ..., Polyk, 'cofactors' = true, A) GCD(Poly1, Poly2, ..., Polyk, 'cofactors' = true, A) GCD['left'](Poly1, Poly2, ..., Polyk, 'cofactors' = true, A) LCM['left'](Poly1, Poly2, ..., Polyk, 'cofactors' = true, A) LCM(Poly1, Poly2, ..., Polyk, 'cofactors' = true, A) LCM['right'](Poly1, Poly2, ..., Polyk, 'cofactors' = true, A) ExtendedGCD['right'](Poly1, Poly2, A, 'c1', 'c2') ExtendedGCD(Poly1, Poly2, A, 'c1', 'c2') ExtendedGCD['left'](Poly1, Poly2, A, 'c1', 'c2')

Parameters

 Poly1, Poly2, ..., Polyk - nonzero Ore polynomials; to define an Ore polynomial, use the OrePoly structure. 'cofactors' = true - (optional) equation; force computation of cofactors A - Ore algebra; to define an Ore algebra, use the SetOreRing function. c1, c2 - (optional) names.

Description

 • The GCD['right'](Poly1, Poly2, ..., Polyk, A) or GCD(Poly1, Poly2, ..., Polyk, A) calling sequence returns the monic GCRD of Poly1, Poly2, ..., Polyk. The GCD['left'](Poly1, Poly2, ..., Polyk, A) calling sequence returns the monic GCLD of Poly1, Poly2, ..., Polyk.
 If the optional 'cofactors = true' equation is specified, the GCD function returns a list in which the first element is the GCRD (resp. GCLD) of the Ore polynomials and the second element is a list of all the left (resp. right) cofactors of the Ore polynomials and the GCRD (resp. GCLD).
 • The LCM['left'](Poly1, Poly2, ..., Polyk, A) or LCM(Poly1, Poly2, ..., Polyk, A) calling sequence returns the monic LCLM of Poly1, Poly2, ..., Polyk. The LCM['right'](Poly1, Poly2, ..., Polyk, A) calling sequence returns the monic LCRM of Poly1, Poly2, ..., Polyk.
 If the optional 'cofactors = true' equation is specified, the LCM function returns a list in which the first element is the LCLM (resp. LCRM) of the Ore polynomials and the second element is a list of all the left (resp. right) cofactors of the LCLM (resp. LCRM) and the Ore polynomials.
 • The ExtendedGCD['right'](Poly1, Poly2, A) or ExtendedGCD(Poly1, Poly2, A) calling sequence returns the monic GCRD of Poly1 and Poly2.
 • The fourth optional argument c1, when present, is assigned a pair [u, v] of Ore polynomials such that (u Poly1 - G) is right divisible by Poly2, where G is the monic GCRD of Poly1 and Poly2; and v Poly1 is the LCLM of Poly1 and Poly2.
 • The fourth and fifth optional arguments c1 and c2, when present, are assigned two pairs [u1, v1] and [u2, v2] of Ore polynomials, respectively. In this case,

$\mathrm{u1}\mathrm{Poly1}+\mathrm{u2}\mathrm{Poly2}=G\mathrm{and}\mathrm{v1}\mathrm{Poly1}+\mathrm{v2}\mathrm{Poly2}=\mathrm{OrePoly}\left(0\right)$

 where G is the monic GCRD of Poly1 and Poly2, v1 Poly1 is the LCLM of Poly1 and Poly2.
 • The ExtendedGCD['left'](Poly1, Poly2, A) calling sequence returns the monic GCLD of Poly1 and Poly2.
 • The fourth optional argument c1, when present, is assigned a pair [u, v] of Ore polynomials such that (Poly1 u - G) is left divisible by Poly2, where G is the monic GCLD of Poly1 and Poly2; and Poly1 v is the LCRM of Poly1 and Poly2.
 • The fourth and fifth optional arguments c1 and c2, when present, are assigned two pairs [u1, v1] and [u2, v2] of Ore polynomials, respectively. In this case,

$\mathrm{Poly1}\mathrm{u1}+\mathrm{Poly2}\mathrm{u2}=G\mathrm{and}\mathrm{Poly1}\mathrm{v1}+\mathrm{Poly2}\mathrm{v2}=\mathrm{OrePoly}\left(0\right)$

 where G is the monic GCLD of Poly1 and Poly2, Poly1 v1 is the LCRM of Poly1 and Poly2.

Examples

 > $\mathrm{with}\left(\mathrm{OreTools}\right):$
 > $A≔\mathrm{SetOreRing}\left(x,'\mathrm{differential}'\right)$
 ${A}{≔}{\mathrm{UnivariateOreRing}}{}\left({x}{,}{\mathrm{differential}}\right)$ (1)
 > $G≔\mathrm{OrePoly}\left(1,3x\right)$
 ${G}{≔}{\mathrm{OrePoly}}{}\left({1}{,}{3}{}{x}\right)$ (2)
 > $\mathrm{Poly1}≔\mathrm{Multiply}\left(\mathrm{OrePoly}\left(\frac{1}{x},0,\frac{{x}^{2}}{x+2}\right),G,A\right)$
 ${\mathrm{Poly1}}{≔}{\mathrm{OrePoly}}{}\left(\frac{{1}}{{x}}{,}{3}{,}\frac{{7}{}{{x}}^{{2}}}{{x}{+}{2}}{,}\frac{{3}{}{{x}}^{{3}}}{{x}{+}{2}}\right)$ (3)
 > $\mathrm{Poly2}≔\mathrm{Multiply}\left(\mathrm{OrePoly}\left(x-1,x\right),G,A\right)$
 ${\mathrm{Poly2}}{≔}{\mathrm{OrePoly}}{}\left({x}{-}{1}{,}{3}{}{{x}}^{{2}}{+}{x}{,}{3}{}{{x}}^{{2}}\right)$ (4)
 > $\mathrm{GCD}['\mathrm{right}']\left(\mathrm{Poly1},\mathrm{Poly2},A\right)$
 ${\mathrm{OrePoly}}{}\left(\frac{{1}}{{3}{}{x}}{,}{1}\right)$ (5)
 > $\mathrm{GCD}\left(\mathrm{Poly1},G,\mathrm{Poly2},A\right)$
 ${\mathrm{OrePoly}}{}\left(\frac{{1}}{{3}{}{x}}{,}{1}\right)$ (6)
 > $\mathrm{GCD}\left(\mathrm{Poly1},\mathrm{Poly2},G,'\mathrm{cofactors}=\mathrm{true}',A\right)$
 $\left[{\mathrm{OrePoly}}{}\left(\frac{{1}}{{3}{}{x}}{,}{1}\right){,}\left[{\mathrm{OrePoly}}{}\left({3}{,}\frac{{6}{}{{x}}^{{2}}}{{x}{+}{2}}{,}\frac{{3}{}{{x}}^{{3}}}{{x}{+}{2}}\right){,}{\mathrm{OrePoly}}{}\left({3}{}{{x}}^{{2}}{,}{3}{}{{x}}^{{2}}\right){,}{\mathrm{OrePoly}}{}\left({3}{}{x}\right)\right]\right]$ (7)
 > $\mathrm{LCM}\left(\mathrm{Poly1},\mathrm{Poly2},G,A\right)$
 ${\mathrm{OrePoly}}{}\left(\frac{{1}}{{3}}{}\frac{{{x}}^{{5}}{-}{3}{}{{x}}^{{4}}{-}{7}{}{{x}}^{{3}}{+}{15}{}{{x}}^{{2}}{-}{4}}{{{x}}^{{5}}{}\left({{x}}^{{3}}{-}{2}{}{{x}}^{{2}}{+}{x}{+}{2}\right)}{,}\frac{{1}}{{3}}{}\frac{{3}{}{{x}}^{{5}}{-}{5}{}{{x}}^{{4}}{-}{21}{}{{x}}^{{3}}{+}{33}{}{{x}}^{{2}}{+}{16}{}{x}{+}{4}}{{{x}}^{{4}}{}\left({{x}}^{{3}}{-}{2}{}{{x}}^{{2}}{+}{x}{+}{2}\right)}{,}\frac{{1}}{{3}}{}\frac{{7}{}{{x}}^{{5}}{-}{18}{}{{x}}^{{4}}{+}{7}{}{{x}}^{{3}}{+}{12}{}{{x}}^{{2}}{+}{40}{}{x}{+}{12}}{\left({{x}}^{{3}}{-}{2}{}{{x}}^{{2}}{+}{x}{+}{2}\right){}{{x}}^{{3}}}{,}\frac{{1}}{{3}}{}\frac{{3}{}{{x}}^{{4}}{+}{{x}}^{{3}}{-}{17}{}{{x}}^{{2}}{+}{19}{}{x}{+}{32}}{{x}{}\left({{x}}^{{3}}{-}{2}{}{{x}}^{{2}}{+}{x}{+}{2}\right)}{,}{1}\right)$ (8)
 > $H≔\mathrm{ExtendedGCD}['\mathrm{right}']\left(\mathrm{Poly1},\mathrm{Poly2},A,'\mathrm{c1}'\right)$
 ${H}{≔}{\mathrm{OrePoly}}{}\left(\frac{{{x}}^{{3}}{-}{2}{}{{x}}^{{2}}{+}{x}{+}{2}}{{x}{}\left({x}{+}{2}\right)}{,}\frac{{3}{}\left({{x}}^{{3}}{-}{2}{}{{x}}^{{2}}{+}{x}{+}{2}\right)}{{x}{+}{2}}\right)$ (9)
 > $\mathrm{c1}$
 $\left[{\mathrm{OrePoly}}{}\left({1}\right){,}{\mathrm{OrePoly}}{}\left({-}\frac{{{x}}^{{2}}{}\left({{x}}^{{4}}{-}{2}{}{{x}}^{{3}}{-}{7}{}{{x}}^{{2}}{+}{12}{}{x}{+}{4}\right)}{{\left({{x}}^{{3}}{-}{2}{}{{x}}^{{2}}{+}{x}{+}{2}\right)}^{{2}}}{,}{-}\frac{{{x}}^{{2}}{}\left({x}{+}{2}\right)}{{{x}}^{{3}}{-}{2}{}{{x}}^{{2}}{+}{x}{+}{2}}\right)\right]$ (10)

Check result.

 > $\mathrm{Remainder}['\mathrm{right}']\left(\mathrm{Minus}\left(\mathrm{Multiply}\left({\mathrm{c1}}_{1},\mathrm{Poly1},A\right),H\right),\mathrm{Poly2},A\right)$
 ${\mathrm{OrePoly}}{}\left({0}\right)$ (11)
 > $\mathrm{Remainder}\left(\mathrm{Multiply}\left({\mathrm{c1}}_{2},\mathrm{Poly1},A\right),\mathrm{Poly2},A\right)$
 ${\mathrm{OrePoly}}{}\left({0}\right)$ (12)
 > $H≔\mathrm{ExtendedGCD}\left(\mathrm{Poly1},\mathrm{Poly2},A,'\mathrm{c1}','\mathrm{c2}'\right)$
 ${H}{≔}{\mathrm{OrePoly}}{}\left(\frac{{{x}}^{{3}}{-}{2}{}{{x}}^{{2}}{+}{x}{+}{2}}{{x}{}\left({x}{+}{2}\right)}{,}\frac{{3}{}\left({{x}}^{{3}}{-}{2}{}{{x}}^{{2}}{+}{x}{+}{2}\right)}{{x}{+}{2}}\right)$ (13)

Check result.

 > $\mathrm{Minus}\left(\mathrm{Add}\left(\mathrm{Multiply}\left({\mathrm{c1}}_{1},\mathrm{Poly1},A\right),\mathrm{Multiply}\left({\mathrm{c2}}_{1},\mathrm{Poly2},A\right)\right),H\right)$
 ${\mathrm{OrePoly}}{}\left({0}\right)$ (14)
 > $\mathrm{Add}\left(\mathrm{Multiply}\left({\mathrm{c1}}_{2},\mathrm{Poly1},A\right),\mathrm{Multiply}\left({\mathrm{c2}}_{2},\mathrm{Poly2},A\right)\right)$
 ${\mathrm{OrePoly}}{}\left({0}\right)$ (15)
 > $A≔\mathrm{SetOreRing}\left(n,'\mathrm{shift}'\right)$
 ${A}{≔}{\mathrm{UnivariateOreRing}}{}\left({n}{,}{\mathrm{shift}}\right)$ (16)
 > $G≔\mathrm{OrePoly}\left(1,3n-3\right)$
 ${G}{≔}{\mathrm{OrePoly}}{}\left({1}{,}{3}{}{n}{-}{3}\right)$ (17)
 > $\mathrm{Poly1}≔\mathrm{Multiply}\left(G,\mathrm{OrePoly}\left(1,n,{n}^{2}\right),A\right)$
 ${\mathrm{Poly1}}{≔}{\mathrm{OrePoly}}{}\left({1}{,}{4}{}{n}{-}{3}{,}{4}{}{{n}}^{{2}}{-}{3}{,}{3}{}\left({n}{-}{1}\right){}{\left({n}{+}{1}\right)}^{{2}}\right)$ (18)
 > $\mathrm{Poly2}≔\mathrm{Multiply}\left(G,\mathrm{OrePoly}\left(n-1,n\right),G,A\right)$
 ${\mathrm{Poly2}}{≔}{\mathrm{OrePoly}}{}\left({n}{-}{1}{,}{6}{}{{n}}^{{2}}{-}{8}{}{n}{+}{3}{,}{9}{}{{n}}^{{3}}{-}{3}{}{{n}}^{{2}}{-}{3}{,}{9}{}\left({n}{-}{1}\right){}{\left({n}{+}{1}\right)}^{{2}}\right)$ (19)
 > $\mathrm{GCD}['\mathrm{left}']\left(\mathrm{Poly1},\mathrm{Poly2},A\right)$
 ${\mathrm{OrePoly}}{}\left(\frac{{1}}{{3}{}\left({n}{-}{2}\right)}{,}{1}\right)$ (20)
 > $\mathrm{GCD}['\mathrm{left}']\left(\mathrm{Poly1},\mathrm{Poly2},G,'\mathrm{cofactors}=\mathrm{true}',A\right)$
 $\left[{\mathrm{OrePoly}}{}\left(\frac{{1}}{{3}{}\left({n}{-}{2}\right)}{,}{1}\right){,}\left[{\mathrm{OrePoly}}{}\left({3}{}{n}{-}{6}{,}{3}{}{{n}}^{{2}}{-}{6}{}{n}{,}{3}{}\left({n}{-}{2}\right){}{{n}}^{{2}}\right){,}{\mathrm{OrePoly}}{}\left({3}{}{{n}}^{{2}}{-}{9}{}{n}{+}{6}{,}{9}{}{{n}}^{{3}}{-}{33}{}{{n}}^{{2}}{+}{39}{}{n}{-}{18}{,}{9}{}\left({n}{-}{2}\right){}{{n}}^{{2}}\right){,}{\mathrm{OrePoly}}{}\left({3}{}{n}{-}{6}\right)\right]\right]$ (21)
 > $\mathrm{LCM}['\mathrm{right}']\left(\mathrm{Poly1},\mathrm{Poly2},G,A\right)$
 ${\mathrm{OrePoly}}{}\left(\frac{{1}}{{9}}{}\frac{{7}{}{{n}}^{{3}}{-}{66}{}{{n}}^{{2}}{+}{176}{}{n}{-}{117}}{{7}{}{{n}}^{{7}}{-}{171}{}{{n}}^{{6}}{+}{1750}{}{{n}}^{{5}}{-}{9735}{}{{n}}^{{4}}{+}{31813}{}{{n}}^{{3}}{-}{61104}{}{{n}}^{{2}}{+}{63900}{}{n}{-}{28080}}{,}\frac{{1}}{{9}}{}\frac{{49}{}{{n}}^{{5}}{-}{518}{}{{n}}^{{4}}{+}{1972}{}{{n}}^{{3}}{-}{3307}{}{{n}}^{{2}}{+}{2398}{}{n}{-}{648}}{\left({{n}}^{{5}}{-}{15}{}{{n}}^{{4}}{+}{87}{}{{n}}^{{3}}{-}{245}{}{{n}}^{{2}}{+}{336}{}{n}{-}{180}\right){}\left({7}{}{{n}}^{{3}}{-}{38}{}{{n}}^{{2}}{+}{58}{}{n}{-}{27}\right)}{,}\frac{{2}}{{9}}{}\frac{{56}{}{{n}}^{{5}}{-}{297}{}{{n}}^{{4}}{+}{430}{}{{n}}^{{3}}{-}{141}{}{{n}}^{{2}}{+}{48}{}{n}{-}{81}}{\left({{n}}^{{3}}{-}{8}{}{{n}}^{{2}}{+}{20}{}{n}{-}{16}\right){}{n}{}\left({7}{}{{n}}^{{2}}{-}{17}{}{n}{+}{3}\right){}\left({n}{-}{1}\right)}{,}\frac{{1}}{{9}}{}\frac{{105}{}{{n}}^{{5}}{-}{122}{}{{n}}^{{4}}{-}{291}{}{{n}}^{{3}}{+}{260}{}{{n}}^{{2}}{+}{171}{}{n}{-}{144}}{\left({{n}}^{{3}}{-}{5}{}{{n}}^{{2}}{+}{7}{}{n}{-}{3}\right){}{n}{}\left({7}{}{{n}}^{{2}}{-}{3}{}{n}{-}{7}\right)}{,}\frac{{1}}{{3}}{}\frac{{21}{}{{n}}^{{5}}{+}{47}{}{{n}}^{{4}}{-}{8}{}{{n}}^{{3}}{-}{70}{}{{n}}^{{2}}{+}{4}{}{n}{+}{21}}{\left({n}{-}{2}\right){}\left({7}{}{{n}}^{{2}}{+}{11}{}{n}{-}{3}\right){}{{n}}^{{2}}}{,}{1}\right)$ (22)
 > $H≔\mathrm{ExtendedGCD}['\mathrm{left}']\left(\mathrm{Poly1},\mathrm{Poly2},A,'\mathrm{c1}'\right)$
 ${H}{≔}{\mathrm{OrePoly}}{}\left(\frac{{1}}{{3}{}\left({n}{-}{2}\right)}{,}{1}\right)$ (23)
 > $\mathrm{c1}$
 $\left[{\mathrm{OrePoly}}{}\left(\frac{{1}}{{3}}{}\frac{{9}{}{{n}}^{{4}}{-}{96}{}{{n}}^{{3}}{+}{373}{}{{n}}^{{2}}{-}{633}{}{n}{+}{401}}{{7}{}{{n}}^{{5}}{-}{94}{}{{n}}^{{4}}{+}{492}{}{{n}}^{{3}}{-}{1259}{}{{n}}^{{2}}{+}{1580}{}{n}{-}{780}}{,}\frac{{3}{}{{n}}^{{2}}{-}{8}{}{n}{+}{3}}{{7}{}{{n}}^{{3}}{-}{45}{}{{n}}^{{2}}{+}{89}{}{n}{-}{54}}\right){,}{\mathrm{OrePoly}}{}\left(\frac{{1}}{{27}}{}\frac{\left({9}{}{{n}}^{{5}}{-}{111}{}{{n}}^{{4}}{+}{517}{}{{n}}^{{3}}{-}{1129}{}{{n}}^{{2}}{+}{1148}{}{n}{-}{434}\right){}\left({3}{}{{n}}^{{2}}{-}{14}{}{n}{+}{14}\right){}\left({3}{}{{n}}^{{2}}{-}{20}{}{n}{+}{31}\right)}{\left({7}{}{{n}}^{{4}}{-}{80}{}{{n}}^{{3}}{+}{332}{}{{n}}^{{2}}{-}{595}{}{n}{+}{390}\right){}\left({7}{}{{n}}^{{5}}{-}{94}{}{{n}}^{{4}}{+}{492}{}{{n}}^{{3}}{-}{1259}{}{{n}}^{{2}}{+}{1580}{}{n}{-}{780}\right)}{,}\frac{{1}}{{27}}{}\frac{\left({21}{}{{n}}^{{4}}{-}{212}{}{{n}}^{{3}}{+}{762}{}{{n}}^{{2}}{-}{1165}{}{n}{+}{648}\right){}{\left({3}{}{{n}}^{{2}}{-}{8}{}{n}{+}{3}\right)}^{{2}}{}{\left({3}{}{{n}}^{{2}}{-}{14}{}{n}{+}{14}\right)}^{{2}}}{\left({7}{}{{n}}^{{4}}{-}{80}{}{{n}}^{{3}}{+}{332}{}{{n}}^{{2}}{-}{595}{}{n}{+}{390}\right){}\left({7}{}{{n}}^{{2}}{-}{31}{}{n}{+}{27}\right){}\left({7}{}{{n}}^{{5}}{-}{59}{}{{n}}^{{4}}{+}{186}{}{{n}}^{{3}}{-}{277}{}{{n}}^{{2}}{+}{197}{}{n}{-}{54}\right)}{,}\frac{{1}}{{9}}{}\frac{{\left({3}{}{{n}}^{{2}}{-}{2}{}{n}{-}{2}\right)}^{{2}}{}{\left({3}{}{{n}}^{{2}}{-}{8}{}{n}{+}{3}\right)}^{{2}}}{\left({7}{}{{n}}^{{2}}{-}{17}{}{n}{+}{3}\right){}{{n}}^{{2}}{}\left({7}{}{{n}}^{{3}}{-}{45}{}{{n}}^{{2}}{+}{89}{}{n}{-}{54}\right)}\right)\right]$ (24)

Check result.

 > $\mathrm{Remainder}['\mathrm{left}']\left(\mathrm{Minus}\left(\mathrm{Multiply}\left(\mathrm{Poly1},{\mathrm{c1}}_{1},A\right),H\right),\mathrm{Poly2},A\right)$
 ${\mathrm{OrePoly}}{}\left({0}\right)$ (25)
 > $\mathrm{Remainder}['\mathrm{left}']\left(\mathrm{Multiply}\left(\mathrm{Poly1},{\mathrm{c1}}_{2},A\right),\mathrm{Poly2},A\right)$
 ${\mathrm{OrePoly}}{}\left({0}\right)$ (26)
 > $H≔\mathrm{ExtendedGCD}['\mathrm{left}']\left(\mathrm{Poly1},\mathrm{Poly2},A,'\mathrm{c1}','\mathrm{c2}'\right)$
 ${H}{≔}{\mathrm{OrePoly}}{}\left(\frac{{1}}{{3}{}\left({n}{-}{2}\right)}{,}{1}\right)$ (27)

Check result.

 > $\mathrm{Minus}\left(\mathrm{Add}\left(\mathrm{Multiply}\left(\mathrm{Poly1},{\mathrm{c1}}_{1},A\right),\mathrm{Multiply}\left(\mathrm{Poly2},{\mathrm{c2}}_{1},A\right)\right),H\right)$
 ${\mathrm{OrePoly}}{}\left({0}\right)$ (28)
 > $\mathrm{Add}\left(\mathrm{Multiply}\left(\mathrm{Poly1},{\mathrm{c1}}_{2},A\right),\mathrm{Multiply}\left(\mathrm{Poly2},{\mathrm{c2}}_{2},A\right)\right)$
 ${\mathrm{OrePoly}}{}\left({0}\right)$ (29)

References

 Abramov, S.A.; Le, H.Q.; and Li, Z. "OreTools: a computer algebra library for univariate Ore polynomial rings." Technical Report CS-2003-12. School of Computer Science, University of Waterloo, 2003.
 Li, Z., and Nemes, I. "A modular algorithm for computing greatest common right divisors of Ore polynomials." Proc. of ISSAC'97, pp. 282-289. Edited by W. Kuechlin. ACM Press, 1997.