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

  

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

Parameters

Description

Examples

References

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:

ASetOreRingx,'differential'

A:=UnivariateOreRingx,differential

(1)

GOrePoly1,3x

G:=OrePoly1,3x

(2)

Poly1MultiplyOrePoly1x,0,x2x+2,G,A

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

(3)

Poly2MultiplyOrePolyx1,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)

HExtendedGCD['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)

HExtendedGCDPoly1,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)

ASetOreRingn,'shift'

A:=UnivariateOreRingn,shift

(16)

GOrePoly1,3n3

G:=OrePoly1,3n3

(17)

Poly1MultiplyG,OrePoly1,n,n2,A

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

(18)

Poly2MultiplyG,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)

HExtendedGCD['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)

HExtendedGCD['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)

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.

See Also

OreTools

OreTools/Euclidean

OreTools/OreAlgebra

OreTools/OrePoly

OreTools[SetOreRing]

 


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