GCD of two polynomials with respect to a regular chain
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)
polynomial of R
variable of R
regular chain of R
subresultant chain of two polynomials
boolean flag (optional)
The command RegularGcd(p1, p2, v, rc, R) returns a list of pairs gi,rci where gi is a non-zero polynomial of R and rci is a regular chain of R.
v 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.
For each returned pair, the polynomial gi is a GCD of p1 and p2 modulo the saturated ideal of rci, in the following sense. First, the leading coefficient of the polynomial gi with respect to v is regular modulo the saturated ideal of rci. Secondly, the polynomial gi belongs to the ideal generated by p1 and p2 and the saturated ideal of rci. Thirdly, if the polynomial gi has positive degree with respect to v, then the pseudo-remainders of both p1 and p2 by gi are null modulo the the saturated ideal of rci. This idea of polynomial GCD modulo the saturated ideal of a regular chain extends the usual notion of polynomial GCDs to non-integral domains.
The returned regular chains rci 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.
R ≔ PolynomialRing⁡y,x
rc ≔ Chain⁡x2+1,Empty⁡R,R
Compute a GCD of p1 and p2 with respect to rc. The example is made such that y+1 is a GCD.
p1 ≔ expand⁡x+1⁢y+x⁢y+1
p2 ≔ expand⁡x−1⁢y+x⁢y+1
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 2⁢x is a unit with respect to rc, so the expected and the computed GCDs are in fact associative. Therefore, the computed polynomial is correct.
out ≔ RegularGcd⁡p1,p2,y,rc,R;factor⁡out11
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
mx ≔ x2−2
rc ≔ Chain⁡mx,Empty⁡R,R
my ≔ expand⁡y−x⁢y+x−1
my ≔ SparsePseudoRemainder⁡my,rc,R
rc ≔ Chain⁡my,rc,R
p1 ≔ y−x⁢z+y+x−1⁢z+1
p2 ≔ y−x⋅1+y+x−1⁢z+1
out_gcd ≔ RegularGcd⁡p1,p2,z,rc,R
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 z.
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.
Download Help Document