|
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,
|
|
|
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,
|
|
|
where G is the monic GCLD of Poly1 and Poly2, Poly1 v1 is the LCRM of Poly1 and Poly2.
|
|
|
|
Examples
|
|
|
>
|
|
|
>
|
|
|
| (1) |
|
>
|
|
|
| (2) |
|
>
|
|
|
| (3) |
|
>
|
|
|
| (4) |
|
>
|
](/support/helpjp/helpview.aspx?si=7363/file02448/math279.png)
|
|
| (5) |
|
>
|
|
|
| (6) |
|
>
|
|
|
![[OrePoly((1/3)/x, 1), [OrePoly(3, 6*x^2/(x+2), 3*x^3/(x+2)), OrePoly(3*x^2, 3*x^2), OrePoly(3*x)]]](/support/helpjp/helpview.aspx?si=7363/file02448/math296.png)
| (7) |
|
>
|
|
|
| (8) |
|
>
|
](/support/helpjp/helpview.aspx?si=7363/file02448/math307.png)
|
|
| (9) |
|
>
|
|
|
![[OrePoly(1), OrePoly(-x^2*(-7*x^2+12*x+x^4+4-2*x^3)/(x+2-2*x^2+x^3)^2, -x^2*(x+2)/(x+2-2*x^2+x^3))]](/support/helpjp/helpview.aspx?si=7363/file02448/math317.png)
| (10) |
Check result.
|
>
|
, H), Poly2, A)](/support/helpjp/helpview.aspx?si=7363/file02448/math323.png)
|
|
| (11) |
|
>
|
![Remainder(Multiply(c1[2], Poly1, A), Poly2, A)](/support/helpjp/helpview.aspx?si=7363/file02448/math330.png)
|
|
| (12) |
|
>
|
|
|
| (13) |
Check result.
|
>
|
![Minus(Add(Multiply(c1[1], Poly1, A), Multiply(c2[1], Poly2, A)), H)](/support/helpjp/helpview.aspx?si=7363/file02448/math346.png)
|
|
| (14) |
|
>
|
![Add(Multiply(c1[2], Poly1, A), Multiply(c2[2], Poly2, A))](/support/helpjp/helpview.aspx?si=7363/file02448/math353.png)
|
|
| (15) |
|
>
|
|
|
| (16) |
|
>
|
|
|
| (17) |
|
>
|
|
|
| (18) |
|
>
|
|
|
| (19) |
|
>
|
](/support/helpjp/helpview.aspx?si=7363/file02448/math388.png)
|
|
| (20) |
|
>
|
](/support/helpjp/helpview.aspx?si=7363/file02448/math395.png)
|
|
![[OrePoly((1/3)/(n-2), 1), [OrePoly(3*n-6, 3*n^2-6*n, 3*(n-2)*n^2), OrePoly(3*n^2-9*n+6, 9*n^3-33*n^2+39*n-18, 9*(n-2)*n^2), OrePoly(3*n-6)]]](/support/helpjp/helpview.aspx?si=7363/file02448/math398.png)
| (21) |
|
>
|
](/support/helpjp/helpview.aspx?si=7363/file02448/math402.png)
|
|
| (22) |
|
>
|
](/support/helpjp/helpview.aspx?si=7363/file02448/math409.png)
|
|
| (23) |
|
>
|
|
|
| (24) |
Check result.
|
>
|
, H), Poly2, A)](/support/helpjp/helpview.aspx?si=7363/file02448/math425.png)
|
|
| (25) |
|
>
|
, Poly2, A)](/support/helpjp/helpview.aspx?si=7363/file02448/math432.png)
|
|
| (26) |
|
>
|
](/support/helpjp/helpview.aspx?si=7363/file02448/math439.png)
|
|
| (27) |
Check result.
|
>
|
![Minus(Add(Multiply(Poly1, c1[1], A), Multiply(Poly2, c2[1], A)), H)](/support/helpjp/helpview.aspx?si=7363/file02448/math448.png)
|
|
| (28) |
|
>
|
![Add(Multiply(Poly1, c1[2], A), Multiply(Poly2, c2[2], A))](/support/helpjp/helpview.aspx?si=7363/file02448/math455.png)
|
|
| (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.
|
|
|
