|
RegularChains[RegularGcd] - GCD of two polynomials with respect to a regular chain
|
|
Calling Sequence
|
|
RegularGcd(p1, p2, v, rc, R)
RegularGcd(p1, p2, v, rc, R, 'normalized'='yes')
RegularGcd(p1, p2, v, rc, R, 'normalized'='strongly')
RegularGcd(src, rc, R)
|
|
|
Parameters
|
|
|
p1
|
-
|
polynomial of R
|
|
p2
|
-
|
polynomial of R
|
|
v
|
-
|
variable of R
|
|
rc
|
-
|
regular chain of R
|
|
R
|
-
|
polynomial ring
|
|
src
|
-
|
subresultant chain of two polynomials
|
|
'normalized'='yes'
|
-
|
boolean flag (optional)
|
|
'normalized'='strongly'
|
-
|
boolean flag (optional)
|
|
|
|
|
|
Description
|
|
|
•
|
 must be the common main variable of p1 and p2.
|
|
•
|
The initials of p1 and p2 must be regular with respect to rc. In order to check this condition, use the command IsRegular. If condition does not hold, then the command RegularizeInitial must be used to split the problem into sub-problems where all the requirements are met.
|
|
•
|
The returned regular chains ![rc[i]](/support/helpjp/helpview.aspx?si=5367/file02694/math225.png) form a triangular decomposition of rc in the sense of Kalkbrener. See the page RegularChains for the concept of a triangular decomposition.
|
|
•
|
If the option 'normalized'='yes' is present, then the returned regular chains are normalized. See ChainTools for the concepts of normalized and strongly normalized regular chain.
|
|
•
|
If 'normalized'='yes' is present, then rc must be normalized.
|
|
•
|
If the option 'normalized'='strongly' is present, then the returned regular chains are strongly normalized.
|
|
•
|
If 'normalized'='strongly' is present, then rc must be strongly normalized.
|
|
•
|
For more details on the specifications and the algorithm, refer to the paper "On triangular decompositions of algebraic varieties" by M. Moreno Maza, available at the author's web page.
|
|
•
|
The command RegularGcd(src, rc, R) has the same specification as RegularGcd(p1, p2, v, rc, R) where src is the subresultant chain returned by SubresultantChain(f1, f2, v, R). In this case, the algorithm is that of X. Li, M. Moreno Maza and W. Pan from the paper "Computations modulo regular chains". This requires that the resultant of f1 and f2 is zero modulo the saturated ideal of this regular chain. See the command SubresultantChain for details and an example.
|
|
•
|
When R has prime characteristic, an algorithm based on modular techniques and asymptotically fast polynomial arithmetic is available through the command RegularGcdBySpecializationCube. Here again the reference is "Computations modulo regular chains" by X. Li, M. Moreno Maza and W. Pan.
|
|
|
|
Examples
|
|
|
>
|
 
|
|
>
|
![R := PolynomialRing([y, x])](/support/helpjp/helpview.aspx?si=5367/file02694/math293.png)
|
|
| (1) |
|
>
|
![rc := Chain([x^2+1], Empty(R), R)](/support/helpjp/helpview.aspx?si=5367/file02694/math300.png)
|
|
| (2) |
Compute a GCD of p1 and p2 with respect to rc. The example is made such that  is a GCD.
|
>
|
|
|
| (3) |
|
>
|
|
|
| (4) |
In general, the output of a GCD computation with respect to a regular chain is a list of regular chains. In this example, we know that no splits can happen since rc defines a field. Now, observe that the output is not exactly the one expected. However, this extraneous factor  is a unit with respect to rc, so the expected and the computed GCDs are in fact associative. Therefore, the computed polynomial is correct.
|
>
|
 ![factor(out[1][1])](/support/helpjp/helpview.aspx?si=5367/file02694/math340.png)
|
|
| (5) |
Let us produce a splitting by computing a GCD. To do so, we need to create a regular chain which is splittable. Now, remember that Construct may split. Hence, we need an example that will not cause a split at construction but which will cause a split when involved in a GCD computation. We use three variables. Two of these variables are used for building a regular chain with two polynomials.
|
>
|
![R := PolynomialRing([z, y, x])](/support/helpjp/helpview.aspx?si=5367/file02694/math354.png)
|
|
| (6) |
|
>
|
|
|
| (7) |
|
>
|
![rc := Chain([mx], Empty(R), R)](/support/helpjp/helpview.aspx?si=5367/file02694/math368.png)
|
|
| (8) |
|
>
|
|
|
| (9) |
|
>
|
|
|
| (10) |
|
>
|
![rc := Chain([my], rc, R)](/support/helpjp/helpview.aspx?si=5367/file02694/math389.png)
|
|
| (11) |
|
>
|
|
|
| (12) |
|
>
|
|
|
| (13) |
|
>
|
|
|
![out_gcd := [[(y+x-1)*z+2*y-1, regular_chain], [3*y^2+(-2*x-2)*y-x^2+2*x, regular_chain]]](/support/helpjp/helpview.aspx?si=5367/file02694/math413.png)
| (14) |
Two cases are obtained. The desired result (up to a multiplicative factor which is a unit) has been obtained as the first GCD. Note that, as expected, the second GCD is a constant with respect to the variable  .
|
|
|
See Also
|
|
Chain, ChainTools, Empty, ExtendedRegularGcd, IsRegular, LastSubresultant, PolynomialRing, RegularChains, RegularGcdBySpecializationCube, Regularize, RegularizeInitial, ResultantBySpecializationCube, SparsePseudoRemainder, SubresultantChain, SubresultantChainSpecializationCube, SubresultantOfIndex
|
|
|
References
|
|
|
|
Kalkbrener, M. "A generalized Euclidean algorithm for computing triangular representations of algebraic varieties." J. Symb. Comp., Vol. 15. (1993): 143-167.
|
|
|
Moreno Maza, M. "On Triangular Decompositions of Algebraic Varieties." MEGA-2000 conference. Bath, UK, England.
|
|
|
Moreno Maza, M. and Rioboo, R. "Polynomial GCD computations over towers of algebraic extensions" In proc. of AAECC-11, Lecture Notes in Comput. Sci, Vol. 948, Springer, 1995.
|
|
|
X. Li, M. Moreno Maza and W. Pan. "Computations modulo regular chains." In proc. of ISSAC 2009, ACM Press.
|
|
|
