RightEuclidean - Maple Help

OreTools[FractionFree]

 RightEuclidean
 return the subresultant sequence of first kind
 RightPseudoQuotient
 return the right pseudo-quotient
 RightPseudoRemainder
 return the right pseudo-remainder

 Calling Sequence RightEuclidean(Poly1, Poly2, A, 'c1', 'c2') RightPseudoRemainder(Poly1, Poly2, A, 'mult', 'pquo') RightPseudoQuotient(Poly1, Poly2, A, 'mult', 'prem')

Parameters

 Poly1, Poly2 - Ore polynomials; to define an Ore polynomial, use the OrePoly structure. A - Ore algebra; to define an Ore algebra, use the SetOreRing function. c1, c2, mult, pquo, prem - (optional) unevaluated names.

Description

 • The RightEuclidean(Poly1, Poly2, A) calling sequence returns a list [m, S] where m is a positive integer and S is an array with m elements storing the subresultant sequence of the first kind of Poly1 and Poly2.
 If Poly1 and Poly2 are fraction-free, and the commutation rule of the Ore algebra A are also fraction-free, then the output of RightEuclidean is fraction-free.
 • If the optional fourth argument to the RightEuclidean command c1 is specified, the first co-sequence of Poly1 and Poly2 is assigned to c1, so that:

${\mathrm{c1}}_{i}\mathrm{Poly2}={S}_{i}\mathrm{mod Poly}1,\left(i=1,2,\mathrm{...},m\right)$

 and c1[m+1] Poly2 is a least common left multiple (LCLM) of Poly1 and Poly2.
 • If the optional fifth argument to the RightEuclidean command c2 is specified, the second co-sequence of Poly1 and Poly2 is assigned to c2, so that:

${\mathrm{c1}}_{i}\mathrm{Poly2}+{\mathrm{c2}}_{i}\mathrm{Poly1}={S}_{i}\left(i=1,2,\mathrm{...},m\right)$

 and c1[m+1] Poly2 = - c2[m+1] Poly1 is an LCLM of Poly1 and Poly2.
 • The RightPseudoRemainder(Poly1, Poly2, A) calling sequence returns the right pseudo-remainder R of Poly1 and Poly2 such that:

$\mathrm{mult Poly}1=\mathrm{pquo Poly}2+R$

 where the degree of R is less than that of Poly2, pquo is the right pseudo-quotient, and mult (the multiplier) is the ${\left(\mathrm{degree}\left(\mathrm{Poly1}\right)-\mathrm{degree}\left(\mathrm{Poly2}\right)+1\right)}^{\mathrm{th}}$ sigma power of the leading coefficient of Poly2.
 If the fourth argument 'mult' is specified, it is assigned the multiplier defined above. If the fifth argument 'pquo' is specified, it is assigned the right pseudo-quotient defined above.
 • The RightPseudoQuotient(Poly1, Poly2, A) calling sequence returns the right pseudo-quotient Q of Poly1 and Poly2 such that:

$\mathrm{mult Poly}1=Q\mathrm{Poly2}+\mathrm{prem}$

 where the degree of the right pseudo-remainder prem is less than that of Poly2 and mult (the multiplier) is the ${\left(\mathrm{degree}\left(\mathrm{Poly1}\right)-\mathrm{degree}\left(\mathrm{Poly2}\right)+1\right)}^{\mathrm{th}}$ sigma power of the leading coefficient of Poly2.
 If the fourth argument 'mult' is specified, it is assigned the multiplier defined above. If the fifth argument 'prem' is specified, it is assigned the right pseudo-remainder defined above.

Examples

 > $\mathrm{with}\left(\mathrm{OreTools}\right):$
 > $\mathrm{with}\left(\mathrm{OreTools}\left[\mathrm{FractionFree}\right]\right):$
 > $A≔\mathrm{SetOreRing}\left(x,'\mathrm{differential}'\right)$
 ${A}{≔}{\mathrm{UnivariateOreRing}}{}\left({x}{,}{\mathrm{differential}}\right)$ (1)
 > $\mathrm{Ore1}≔\mathrm{OrePoly}\left(1,3x,{x}^{2}-\left(1+x\right),23x+1\right)$
 ${\mathrm{Ore1}}{≔}{\mathrm{OrePoly}}{}\left({1}{,}{3}{}{x}{,}{{x}}^{{2}}{-}{x}{-}{1}{,}{23}{}{x}{+}{1}\right)$ (2)
 > $\mathrm{Ore2}≔\mathrm{OrePoly}\left(x,x,{x}^{2}+x+1\right)$
 ${\mathrm{Ore2}}{≔}{\mathrm{OrePoly}}{}\left({x}{,}{x}{,}{{x}}^{{2}}{+}{x}{+}{1}\right)$ (3)
 > $V≔\mathrm{RightEuclidean}\left(\mathrm{Ore2},\mathrm{Ore1},A,'\mathrm{c1}','\mathrm{c2}'\right)$
 ${V}{≔}\left[{4}{,}{S}\right]$ (4)

Check the result

 > $m≔V\left[1\right];$$S≔V\left[2\right]$
 ${m}{≔}{4}$
 ${S}{≔}{S}$ (5)
 > $\mathrm{print}\left(S\right)$
 $\left[\begin{array}{cccc}{\mathrm{OrePoly}}{}\left({1}{,}{3}{}{x}{,}{{x}}^{{2}}{-}{x}{-}{1}{,}{23}{}{x}{+}{1}\right)& {\mathrm{OrePoly}}{}\left({x}{,}{x}{,}{{x}}^{{2}}{+}{x}{+}{1}\right)& {\mathrm{OrePoly}}{}\left({-}{{x}}^{{5}}{+}{{x}}^{{4}}{+}{49}{}{{x}}^{{3}}{+}{7}{}{{x}}^{{2}}{-}{20}{}{x}{,}{2}{}{{x}}^{{5}}{-}{17}{}{{x}}^{{4}}{+}{32}{}{{x}}^{{3}}{-}{14}{}{{x}}^{{2}}{-}{20}{}{x}{-}{1}\right)& {\mathrm{OrePoly}}{}\left({{x}}^{{8}}{+}{3}{}{{x}}^{{7}}{-}{209}{}{{x}}^{{6}}{+}{1005}{}{{x}}^{{5}}{+}{61}{}{{x}}^{{4}}{-}{587}{}{{x}}^{{3}}{+}{971}{}{{x}}^{{2}}{+}{35}{}{x}{-}{20}\right)\end{array}\right]$ (6)
 > $\mathbf{for}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}i\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{to}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}m\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}\mathrm{W1}≔\mathrm{Multiply}\left(\mathrm{c1}\left[i\right],\mathrm{Ore2},A\right);\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}\mathrm{W2}≔\mathrm{Multiply}\left(\mathrm{c2}\left[i\right],\mathrm{Ore1},A\right);\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}W≔\mathrm{Add}\left(\mathrm{W1},\mathrm{W2}\right);\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}C≔\mathrm{Minus}\left(W,S\left[i\right]\right);\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}\mathrm{print}\left(C\right)\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathbf{end}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}:$
 ${\mathrm{OrePoly}}{}\left({0}\right)$
 ${\mathrm{OrePoly}}{}\left({0}\right)$
 ${\mathrm{OrePoly}}{}\left({0}\right)$
 ${\mathrm{OrePoly}}{}\left({0}\right)$ (7)
 > $\mathrm{W3}≔\mathrm{Multiply}\left(\mathrm{c1}\left[m+1\right],\mathrm{Ore2},A\right):$
 > $\mathrm{W4}≔\mathrm{Multiply}\left(\mathrm{c2}\left[m+1\right],\mathrm{Ore1},A\right):$
 > $\mathrm{Add}\left(\mathrm{W3},\mathrm{W4}\right)$
 ${\mathrm{OrePoly}}{}\left({0}\right)$ (8)
 > $\mathrm{Poly1}≔\mathrm{OrePoly}\left(x,0,x+1,x+2\right)$
 ${\mathrm{Poly1}}{≔}{\mathrm{OrePoly}}{}\left({x}{,}{0}{,}{x}{+}{1}{,}{x}{+}{2}\right)$ (9)
 > $\mathrm{Poly2}≔\mathrm{OrePoly}\left(x,x+1,{x}^{2}-1\right)$
 ${\mathrm{Poly2}}{≔}{\mathrm{OrePoly}}{}\left({x}{,}{x}{+}{1}{,}{{x}}^{{2}}{-}{1}\right)$ (10)
 > $B≔\mathrm{SetOreRing}\left(x,'\mathrm{shift}'\right)$
 ${B}{≔}{\mathrm{UnivariateOreRing}}{}\left({x}{,}{\mathrm{shift}}\right)$ (11)
 > $R≔\mathrm{RightPseudoRemainder}\left(\mathrm{Poly1},\mathrm{Poly2},B\right)$
 ${R}{≔}{\mathrm{OrePoly}}{}\left({{x}}^{{5}}{+}{{x}}^{{4}}{-}{3}{}{{x}}^{{3}}{+}{4}{}{x}{,}{-}{2}{}{{x}}^{{4}}{-}{6}{}{{x}}^{{3}}{-}{{x}}^{{2}}{+}{9}{}{x}{+}{6}\right)$ (12)
 > $R≔\mathrm{RightPseudoRemainder}\left(\mathrm{Poly1},\mathrm{Poly2},B,'m','Q'\right)$
 ${R}{≔}{\mathrm{OrePoly}}{}\left({{x}}^{{5}}{+}{{x}}^{{4}}{-}{3}{}{{x}}^{{3}}{+}{4}{}{x}{,}{-}{2}{}{{x}}^{{4}}{-}{6}{}{{x}}^{{3}}{-}{{x}}^{{2}}{+}{9}{}{x}{+}{6}\right)$ (13)
 > $m$
 ${{x}}^{{4}}{+}{2}{}{{x}}^{{3}}{-}{{x}}^{{2}}{-}{2}{}{x}$ (14)
 > $Q$
 ${\mathrm{OrePoly}}{}\left({{x}}^{{3}}{+}{2}{}{{x}}^{{2}}{-}{2}{}{x}{-}{4}{,}\left({{x}}^{{2}}{-}{1}\right){}\left({x}{+}{2}\right)\right)$ (15)

Check the result

 > $\mathrm{evalb}\left(\mathrm{factor}\left(\mathrm{Add}\left(\mathrm{Multiply}\left(Q,\mathrm{Poly2},B\right),R\right)\right)=\mathrm{factor}\left(\mathrm{ScalarMultiply}\left(m,\mathrm{Poly1}\right)\right)\right)$
 ${\mathrm{true}}$ (16)
 > $Q≔\mathrm{RightPseudoQuotient}\left(\mathrm{Poly1},\mathrm{Poly2},A\right)$
 ${Q}{≔}{\mathrm{OrePoly}}{}\left({{x}}^{{3}}{-}{2}{}{{x}}^{{2}}{-}{8}{}{x}{-}{3}{,}\left({{x}}^{{2}}{-}{1}\right){}\left({x}{+}{2}\right)\right)$ (17)
 > $Q≔\mathrm{RightPseudoQuotient}\left(\mathrm{Poly1},\mathrm{Poly2},B,'m','R'\right)$
 ${Q}{≔}{\mathrm{OrePoly}}{}\left({{x}}^{{3}}{+}{2}{}{{x}}^{{2}}{-}{2}{}{x}{-}{4}{,}\left({{x}}^{{2}}{-}{1}\right){}\left({x}{+}{2}\right)\right)$ (18)
 > $m$
 ${{x}}^{{4}}{+}{2}{}{{x}}^{{3}}{-}{{x}}^{{2}}{-}{2}{}{x}$ (19)
 > $R$
 ${\mathrm{OrePoly}}{}\left({{x}}^{{5}}{+}{{x}}^{{4}}{-}{3}{}{{x}}^{{3}}{+}{4}{}{x}{,}{-}{2}{}{{x}}^{{4}}{-}{6}{}{{x}}^{{3}}{-}{{x}}^{{2}}{+}{9}{}{x}{+}{6}\right)$ (20)

Check the result

 > $\mathrm{evalb}\left(\mathrm{factor}\left(\mathrm{Add}\left(\mathrm{Multiply}\left(Q,\mathrm{Poly2},B\right),R\right)\right)=\mathrm{factor}\left(\mathrm{ScalarMultiply}\left(m,\mathrm{Poly1}\right)\right)\right)$
 ${\mathrm{true}}$ (21)

References

 Li, Z. "A subresultant theory for Ore polynomials with applications." Proc. of ISSAC'98. pp. 132-139. Edited by O. Gloor. ACM Press, 1998.