compute greatest common right or left divisor (GCRD or GCLD) of Ore polynomials - Maple Help

Online Help

All Products    Maple    MapleSim


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

OreTools[LCM] - compute least common left or right multiple (LCLM or LCRM) of Ore polynomials

OreTools[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,

u1Poly1+u2Poly2=Gandv1Poly1+v2Poly2=OrePoly0

  

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,

Poly1u1+Poly2u2=GandPoly1v1+Poly2v2=OrePoly0

  

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

Examples

withOreTools:

A:=SetOreRingx,'differential'

A:=UnivariateOreRingx,differential

(1)

G:=OrePoly1,3x

G:=OrePoly1,3x

(2)

Poly1:=MultiplyOrePoly1x,0,x2x+2,G,A

Poly1:=OrePoly1x,3,7x2x+2,3x3x+2

(3)

Poly2:=MultiplyOrePolyx1,x,G,A

Poly2:=OrePolyx1,3x2+x,3x2

(4)

GCD'right'Poly1,Poly2,A

OrePoly13x,1

(5)

GCDPoly1,G,Poly2,A

OrePoly13x,1

(6)

GCDPoly1,Poly2,G,'cofactors=true',A

OrePoly13x,1,OrePoly3,6x2x+2,3x3x+2,OrePoly3x2,3x2,OrePoly3x

(7)

LCMPoly1,Poly2,G,A

OrePoly13x53x47x3+15x24x5x32x2+x+2,133x55x421x3+33x2+16x+4x4x32x2+x+2,137x518x4+7x3+12x2+40x+12x32x2+x+2x3,133x4+x317x2+19x+32xx32x2+x+2,1

(8)

H:=ExtendedGCD'right'Poly1,Poly2,A,'c1'

H:=OrePolyx32x2+x+2xx+2,3x32x2+x+2x+2

(9)

c1

OrePoly1,OrePolyx2x42x37x2+12x+4x32x2+x+22,x2x+2x32x2+x+2

(10)

Check result.

Remainder'right'MinusMultiplyc11,Poly1,A,H,Poly2,A

OrePoly0

(11)

RemainderMultiplyc12,Poly1,A,Poly2,A

OrePoly0

(12)

H:=ExtendedGCDPoly1,Poly2,A,'c1','c2'

H:=OrePolyx32x2+x+2xx+2,3x32x2+x+2x+2

(13)

Check result.

MinusAddMultiplyc11,Poly1,A,Multiplyc21,Poly2,A,H

OrePoly0

(14)

AddMultiplyc12,Poly1,A,Multiplyc22,Poly2,A

OrePoly0

(15)

A:=SetOreRingn,'shift'

A:=UnivariateOreRingn,shift

(16)

G:=OrePoly1,3n3

G:=OrePoly1,3n3

(17)

Poly1:=MultiplyG,OrePoly1,n,n2,A

Poly1:=OrePoly1,4n3,4n23,3n1n+12

(18)

Poly2:=MultiplyG,OrePolyn1,n,G,A

Poly2:=OrePolyn1,6n28n+3,9n33n23,9n1n+12

(19)

GCD'left'Poly1,Poly2,A

OrePoly13n2,1

(20)

GCD'left'Poly1,Poly2,G,'cofactors=true',A

OrePoly13n2,1,OrePoly3n6,3n26n,3n2n2,OrePoly3n29n+6,9n333n2+39n18,9n2n2,OrePoly3n6

(21)

LCM'right'Poly1,Poly2,G,A

OrePoly197n366n2+176n1177n7171n6+1750n59735n4+31813n361104n2+63900n28080,1949n5518n4+1972n33307n2+2398n648n515n4+87n3245n2+336n1807n338n2+58n27,2956n5297n4+430n3141n2+48n81n38n2+20n16n7n217n+3n1,19105n5122n4291n3+260n2+171n144n35n2+7n3n7n23n7,1321n5+47n48n370n2+4n+21n27n2+11n3n2,1

(22)

H:=ExtendedGCD'left'Poly1,Poly2,A,'c1'

H:=OrePoly13n2,1

(23)

c1

OrePoly139n496n3+373n2633n+4017n594n4+492n31259n2+1580n780,3n28n+37n345n2+89n54,OrePoly1279n5111n4+517n31129n2+1148n4343n214n+143n220n+317n480n3+332n2595n+3907n594n4+492n31259n2+1580n780,12721n4212n3+762n21165n+6483n28n+323n214n+1427n480n3+332n2595n+3907n231n+277n559n4+186n3277n2+197n54,193n22n223n28n+327n217n+3n27n345n2+89n54

(24)

Check result.

Remainder'left'MinusMultiplyPoly1,c11,A,H,Poly2,A

OrePoly0

(25)

Remainder'left'MultiplyPoly1,c12,A,Poly2,A

OrePoly0

(26)

H:=ExtendedGCD'left'Poly1,Poly2,A,'c1','c2'

H:=OrePoly13n2,1

(27)

Check result.

MinusAddMultiplyPoly1,c11,A,MultiplyPoly2,c21,A,H

OrePoly0

(28)

AddMultiplyPoly1,c12,A,MultiplyPoly2,c22,A

OrePoly0

(29)

See Also

OreTools, OreTools/Euclidean, OreTools/OreAlgebra, OreTools/OrePoly, OreTools[SetOreRing]

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.


Download Help Document

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam