## Algorithms for computing greatest common divisors of parametric multivariate polynomials.(English)Zbl 1443.13023

Summary: Two new efficient algorithms for computing greatest common divisors (gcds) of parametric multivariate polynomials over $$k[U][X]$$ are presented. The key idea of the first algorithm is that the gcd of two non-parametric multivariate polynomials can be obtained by dividing their product by the generator of the intersection of two principal ideals generated by the polynomials. The second algorithm is based on another simple insight that the gcd can be extracted using the generator of the ideal quotient of a polynomial with respect to the second polynomial. Since the ideal intersection and ideal quotient in these cases are also principal ideals, their generators can be obtained by computing minimal Gröbner bases of the ideal intersection and ideal quotient, respectively. To avoid introducing new variables which can adversely affect the efficiency, minimal Gröbner bases computations are performed on modules. Both of these constructions generalize to the parametric case as shown in the paper. Comprehensive Gröbner system constructions are used for the parametric ideal intersection and ideal quotient using the Kapur-Sun-Wang’s algorithm. It is proved that whether in a minimal comprehensive Gröbner system of a parametric ideal intersection or in that of a parametric ideal quotient, each branch of the specializations corresponds to a principal parametric ideal with a single generator. Using this generator, the parametric gcd of that branch is obtained by division. For the case of more than two parametric polynomials, we can use the above two algorithms to compute gcds recursively, and get an extended algorithm by generalizing the idea of the second algorithm. Algorithms do not suffer from having to apply expensive steps such as ensuring whether parametric polynomials are primitive w.r.t. the main variable as used in both the algorithms proposed by K. Nagasaka [in: Proceedings of the 42nd international symposium on symbolic and algebraic computation, ISSAC 2017, Kaiserslautern, Germany, July 25–28, 2017. New York, NY: Association for Computing Machinery (ACM). 341–348 (2017; Zbl 1458.13037)]. The resulting algorithms are not only conceptually simple to understand but are more efficient in practice. The proposed algorithms and both of Nagasaka’s algorithms have been implemented in Singular, and their performance is compared on a number of examples.

### MSC:

 13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) 68W30 Symbolic computation and algebraic computation

Zbl 1458.13037

### Software:

parametric GCD; SINGULAR
Full Text:

### References:

  Abramov, S.; Kvashenko, K., On the greatest common divisor of polynomials which depend on a parameter, (Proceedings of the 1993 ACM International Symposium on Symbolic and Algebraic Computation (1993)), 152-156 · Zbl 0925.13009  Ayad, A., Complexity of algorithms for computing greatest common divisors of parametric univariate polynomials, Int. J. Algebra, 4, 4, 173-188 (2010) · Zbl 1205.11133  Bayer, D.; Mumford, D., What can be computed in algebraic geometry?, (Eisenbud, D.; Robbiano, L., Computational Algebraic Geometry and Commutative Algebra (1993), Cambridge University Press: Cambridge University Press Cambridge), 1-48 · Zbl 0846.13017  Brown, W., On Euclid’s algorithm and the computation of polynomial greatest common divisors, J. ACM, 18, 478-504 (1971) · Zbl 0226.65040  Cox, D.; Little, J.; O’shea, D., Ideals, Varieties, and Algorithms, Undergraduate Texts in Mathematics (1992), Springer: Springer New York  Cox, D.; Little, J.; O’shea, D., Using Algebraic Geometry, Undergraduate Texts in Mathematics (2005), Springer: Springer New York · Zbl 1079.13017  Decker, W.; Greuel, G.-M.; Pfister, G.; Schoenemann, H., SINGULAR 4.0.3. a computer algebra system for polynomial computations (2016), fb mathematik der universitaet, d-67653 kaiserslautern  Decker, W.; Lossen, C., Computing in Algebraic Geometry: A Quick Start Using SINGULAR, Algorithms and Computation in Mathematics (AACIM), vol. 16 (2006), Springer: Springer New York · Zbl 1095.14001  Dubé, T., The structure of polynomial ideals and Gröbner bases, SIAM J. Comput., 19, 750-775 (1990) · Zbl 0697.68051  Gianni, P.; Trager, B., GCDs and factoring multivariate polynomials using Gröbner bases, (Proceedings of EUROCAL ’85, European Conference on Computer Algebra. Proceedings of EUROCAL ’85, European Conference on Computer Algebra, Lecture Notes in Computer Science, vol. 204 (1985), Springer: Springer Berlin, Heidelberg), 409-410  Kapur, D., An approach for solving systems of parametric polynomial equations, (Saraswat Hentenryck, V., Principles and Practices of Constraint Programming (1995), MIT Press), 217-244  Kapur, D.; Lu, D.; Monagan, M.; Sun, Y.; Wang, D., An efficient algorithm for computing parametric multivariate polynomial GCD, (Proceedings of the 2018 ACM on International Symposium on Symbolic and Algebraic Computation (2018)), 239-246  Kapur, D.; Sun, Y.; Wang, D., A new algorithm for computing comprehensive Gröbner systems, (Proceedings of the 2010 ACM International Symposium on Symbolic and Algebraic Computation (2010)), 29-36 · Zbl 1321.68533  Kapur, D.; Sun, Y.; Wang, D., An efficient algorithm for computing a comprehensive Gröbner system of a parametric polynomial system, J. Symb. Comput., 49, 27-44 (2013) · Zbl 1255.13018  Kapur, D.; Yang, Y., An algorithm for computing a minimal comprehensive Gröbner basis of a parametric polynomial system, (Proceedings of Conference Encuentros de Algebra Computacionaly Aplicaciones (EACA) (2014))  Mayr, E.; Meyer, A., The complexity of the word problems for commutative semigroups and polynomial ideals, Adv. Math., 46, 3, 305-329 (1982) · Zbl 0506.03007  Möller, H.; Mora, F., Upper and lower bounds for the degree of Gröbner bases, (Fitch, J., EUROSAM 1984. EUROSAM 1984, Lecture Notes in Computer Science, vol. 174 (1984), Springer-Verlag: Springer-Verlag New York), 172-183 · Zbl 0564.68030  Montes, A., A new algorithm for discussing Gröbner bases with parameters, J. Symb. Comput., 33, 2, 183-208 (2002) · Zbl 1068.13016  Montes, A.; Schoenemann, H. (2016), grobcov.lib  Moses, J.; Yun, D., The EZ GCD algorithm, (Proceedings of ACM’73 (1973), ACM Press: ACM Press New York), 159-166  Nabeshima, K., On the computation of parametric Gröbner bases for modules and syzygies, Jpn. J. Ind. Appl. Math., 27, 2, 217-238 (2010) · Zbl 1204.13019  Nabeshima, K., Stability Conditions of Monomial Bases and Comprehensive Gröbner Systems, Proceedings of the International Conference on Computer Algebra in Scientific Computing, vol. 7442, 248-259 (2012), Springer-Verlag · Zbl 1373.13030  Nagasaka, K., Parametric greatest common divisors using comprehensive Gröbner systems, (Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation (2017)), 341-348  Sanuki, M.; Inaba, D.; Sasaki, T., Computation of GCD of sparse multivariate polynomials by extended hensel construction, (Proceedings of the 2016 IEEE International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (2016)), 34-41  Sasaki, T.; Suzuki, M., Three new algorithms for multivariate polynomial GCD, J. Symb. Comput., 13, 4, 395-411 (1992) · Zbl 0761.12005  Suzuki, A.; Sato, Y., A simple algorithm to compute comprehensive Gröbner bases using gröbner bases, (Proceedings of the 2006 ACM International Symposium on Symbolic and Algebraic Computation (2006)), 326-331 · Zbl 1356.13040  Weispfenning, V., Comprehensive Gröbner bases, J. Symb. Comput., 14, 3, 669-683 (1992) · Zbl 1054.13015  Zippel, R., Probabilistic algorithms for sparse polynomials, (Proceedings of EUROSAM’79 (1979), Springer-Verlag), 216-226
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.