×

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

Citations:

Zbl 1458.13037
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] 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
[2] 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
[3] 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
[4] Brown, W., On Euclid’s algorithm and the computation of polynomial greatest common divisors, J. ACM, 18, 478-504 (1971) · Zbl 0226.65040
[5] Cox, D.; Little, J.; O’shea, D., Ideals, Varieties, and Algorithms, Undergraduate Texts in Mathematics (1992), Springer: Springer New York
[6] Cox, D.; Little, J.; O’shea, D., Using Algebraic Geometry, Undergraduate Texts in Mathematics (2005), Springer: Springer New York · Zbl 1079.13017
[7] 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
[8] 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
[9] Dubé, T., The structure of polynomial ideals and Gröbner bases, SIAM J. Comput., 19, 750-775 (1990) · Zbl 0697.68051
[10] 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
[11] 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
[12] 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
[13] 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
[14] 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
[15] 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))
[16] 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
[17] 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
[18] Montes, A., A new algorithm for discussing Gröbner bases with parameters, J. Symb. Comput., 33, 2, 183-208 (2002) · Zbl 1068.13016
[19] Montes, A.; Schoenemann, H. (2016), grobcov.lib
[20] Moses, J.; Yun, D., The EZ GCD algorithm, (Proceedings of ACM’73 (1973), ACM Press: ACM Press New York), 159-166
[21] 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
[22] 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
[23] 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
[24] 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
[25] Sasaki, T.; Suzuki, M., Three new algorithms for multivariate polynomial GCD, J. Symb. Comput., 13, 4, 395-411 (1992) · Zbl 0761.12005
[26] 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
[27] Weispfenning, V., Comprehensive Gröbner bases, J. Symb. Comput., 14, 3, 669-683 (1992) · Zbl 1054.13015
[28] 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.