×

A survey on algorithms for computing comprehensive Gröbner systems and comprehensive Gröbner bases. (English) Zbl 1417.68295

Summary: V. Weispfenning in [J. Symb. Comput. 14, No. 1, 1–29 (1992; Zbl 0784.13013)] introduced the concepts of comprehensive Gröbner system/basis of a parametric polynomial system, and he also presented an algorithm to compute them. Since then, this research field has attracted much attention over the past several decades, and many efficient algorithms have been proposed. Moreover, these algorithms have been applied to many different fields, such as parametric polynomial equations solving, geometric theorem proving and discovering, quantifier elimination, and so on. This survey brings together the works published between 1992 and 2018, and we hope that this survey is valuable for this research area.

MSC:

68W30 Symbolic computation and algebraic computation
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
68-02 Research exposition (monographs, survey articles) pertaining to computer science

Citations:

Zbl 0784.13013

Software:

PGB; dpgb; parametric GCD
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Donald, B. R.; Kapur, D.; Mundy, J. L., Symbolic and numerical computation for artificial intelligence, 52-55, (1992), Orlando, Florida
[2] Gao, X. S.; Chou, S. C., Solving parametric algebraic systems, 335-341, (1992), New York · Zbl 0925.13014
[3] William, Y. S., An algorithm for solving parametric linear systems, Journal of Symbolic Computation, 13, 353-394, (1992) · Zbl 0752.34010
[4] Chen, C.; Golubitsky, O.; Lemaire, F.; etal., Comprehensive triangular decomposition, 73-101, (2007), Berlin · Zbl 1141.68677
[5] Lazard, D.; Rouillier, F., Solving parametric polynomial systems, Journal of Symbolic Computation, 42, 636-667, (2007) · Zbl 1156.14044
[6] Huang, Z., Parametric equation solving and quantifier elimination in finite fields with the characteristic set method, Journal of Systems Science and Complexity, 25, 778-791, (2012) · Zbl 1292.93047
[7] Chen, Z. H.; Tang, X. X.; Xia, B. C., Generic regular decompositions for parametric polynomial systems, Journal of Systems Science and Complexity, 28, 1194-1211, (2015) · Zbl 1327.93101
[8] Chen, X. F.; Li, P.; Lin, L.; etal., Proving geometric theorems by partitioned-parametric Gröbner bases, 34-43, (2004)
[9] Lin L, Automated geometric theorem proving and parametric polynomial equations solving, Master Degree Thesis, Institute of Systems Science, CAS, Beijing, 2006.
[10] Wang, D. K.; Lin, L., Automatic discovering of geometric theorems by computing Gröbner bases with parameters, (2005)
[11] Montes, A.; Recio, T., Automatic discovery of geometry theorems using minimal canonical comprehensive Gröbner systems, 113-138, (2006) · Zbl 1195.68093
[12] Zhou, J.; Wang, D. K.; Sun, Y., Automated reducible geometric theorem proving and discovery by Gröbner basis method, Journal of Autotamed Reasoning, 59, 331-344, (2017) · Zbl 1425.68383
[13] Botana, F.; Montes, A.; Recio, T., An algorithm for automatic discovery of algebraic loci, 53-59, (2012)
[14] Gao, X. S.; Hou, X.; Tang, J.; etal., Complete solution classification for the perspective-three-point problem, IEEE Trans. Pattern Anal. Mach. Intell., 25, 930-943, (2003)
[15] Zhou, J.; Wang, D. K., Solving the perspective-three-point problem using comprehensive Gröbner systems, Journal of Systems Science and Complexity, 29, 1446-1471, (2016) · Zbl 1388.13059
[16] Weispfenning, V., A new approach to quantifier elimination for real algebra, 376-392, (1998) · Zbl 0900.03046
[17] Kapur, D., A quantifier-elimination based heuristic for automatically generating inductive assertions for programs, Journal of Systems Science and Complexity, 19, 307-330, (2006) · Zbl 1115.68051
[18] Fukasaku, R.; Iwane, H.; Sato, Y., Real quantifier elimination by computation of comprehensive Gröbner systems, 173-180, (2015), Bath · Zbl 1345.68282
[19] Fukasaku, R.; Inoue, S.; Sato, Y., On QE algorithms over an algebraically closed field based on comprehensive Gröbner systems, Mathematics in Computer Science, 9, 267-281, (2015) · Zbl 1341.68311
[20] Fukasaku, R.; Iwane, H.; Sato, Y., Improving a CGS-QE algorithm, 231-235, (2015), New York · Zbl 1460.13051
[21] Fukasaku, R.; Iwane, H.; Sato, Y., On the implementation of CGS real QE, 165-172, (2016) · Zbl 1434.68705
[22] Weispfenning, V., Comprehensive Gröbner bases, Journal of Symbolic Computation, 14, 1-29, (1992) · Zbl 0784.13013
[23] Pesh M, Computing comprehensive Gröbner bases using MAS, User Manual, 1994.
[24] Kapur, D., An approach for solving systems of parametric polynomial equations, 217-224, (1995), Massachusetts
[25] Montes, A., A new algorithm for discussing Gröbner bases with parameters, Journal of Symbolic Computation, 33, 183-208, (2002) · Zbl 1068.13016
[26] Weispfenning, V., Canonical comprehensive Gröbner bases, 270-276, (2002), New York · Zbl 1072.68702
[27] Weispfenning, V., Canonical comprehensive Gröbner bases, Journal of Symbolic Computation, 36, 669-683, (2003) · Zbl 1054.13015
[28] Manubens, M.; Montes, A., Improving DISPGB algorithm using the discriminant ideal, J. Symbolic. Comput., 41, 1245-1263, (2006) · Zbl 1121.13031
[29] Suzuki, A.; Sato, Y., An alternative approach to comprehensive Gröbner bases, J. Symbolic. Comput., 36, 649-667, (2003) · Zbl 1053.13013
[30] Suzuki, A.; Sato, Y., Comprehensive Gröbner bases via ACGB, 65-73, (2004)
[31] Wibmer, M., Gröbner bases for families of affine or projective schemes, J. Symbolic. Comput., 42, 803-834, (2007) · Zbl 1134.13025
[32] Manubens, M.; Montes, A., Minimal canonical comprehensive Gröbner system, J. Symbolic. Comput., 44, 463-478, (2009) · Zbl 1159.13304
[33] Montes, A.; Wibmer, M., Gröbner bases for polynomial systems with parameters, J. Symbolic. Comput., 45, 1391-1425, (2010) · Zbl 1207.13018
[34] Suzuki, A.; Sato, Y., A simple algorithm to compute comprehensive Gröbner bases using Gröbner bases, 326-331, (2006) · Zbl 1356.13040
[35] Kalkbrener, M., On the stability of Gröbner bases under specializations, Journal of Symbolic Computation, 24, 51-58, (1997) · Zbl 1054.13502
[36] Nabeshima, K., A speed-up of the algorithm for computing comprehensive Gröbner systems, 299-306, (2007) · Zbl 1190.13025
[37] Kapur, D.; Sun, Y.; Wang, D. K., A new algorithm for computing comprehensive Gröbner systems, 29-36, (2010) · Zbl 1321.68533
[38] Kapur, D.; Sun, Y.; Wang, D. K., An efficient algorithm for computing a comprehensive Gröbner system of a parametric polynomial systems, Journal of Symbolic Computation, 49, 27-44, (2010) · Zbl 1255.13018
[39] Kapur, D.; Sun, Y.; Wang, D. K., Computing comprehensive Gröbner systems and comprehensive Gröbner bases simultaneously, 193-200, (2011) · Zbl 1323.13004
[40] Kapur, D.; Sun, Y.; Wang, D. K., An efficient method for computing comprehensive Gröbner bases, Journal of Symbolic Computation, 52, 124-142, (2013) · Zbl 1283.13024
[41] Kapur, D.; Yang, Y., An algorithm for computing a minimal comprehensive Gröbner basis of a parametric polynomial system, 21-25, (2014), Barcelona, Spain
[42] Kapur, D.; Yang, Y., An algorithm to check whether a basis of a parametric polynomial system is a comprehensive Gröbner basis and the associated completion algorithm, 243-250, (2015) · Zbl 1346.13059
[43] Kapur, D., Comprehensive Gröbner basis theory for a parametric polynomial ideal and the associated completion algorithm, Journal of Systems Science and Complexity, 30, 196-233, (2017) · Zbl 1376.13012
[44] Hashemi, A.; Darmian, M. D.; Barkhordar, M., Gröbner systems conversion, Mathematics in Computer Science, 11, 61-77, (2017) · Zbl 1409.68344
[45] Fukuda, K.; Jensen, A.; Lauritzen, N.; etal., The generic Gröbner walk, J. Symb. Comput., 42, 298-312, (2007) · Zbl 1124.68120
[46] Hashemi, A.; Darmian, M. D.; Barkhordar, M., Universal Gröbner basis for parametric polynomial ideals, 191-199, (2018), Cham · Zbl 1395.13027
[47] Kurata, Y., Improving Suzuki-Sato’s CGS algorithm by using stability of Gröbner bases and basic manipulations for efficient implementation, Communications of the Japan Society for Symbolic and Algebraic Computation, 1, 39-66, (2011)
[48] Wu, W. T., On the decision problem and the mechanization of theorem proving in elementary geometry, Sci. Sin., 21, 159-172, (1978) · Zbl 0376.68057
[49] Wu, W. T., Basic principles of mechanical theorem proving in elementary geometries, J. Autom. Reason, 2, 221-252, (1986) · Zbl 0642.68163
[50] Cox D, Little J, and O’shea D, Ideals, Varieties, and Algorithms, Springer, New York, 1992. · Zbl 0756.13017
[51] Caviness B F and Johnson J R, Quantifier Elimination and Cylindrical Algebraic Decomposition, Springer Science and Business Media, New York, 2012.
[52] Collins, G. E., Quantifier elimination for real closed fields by cylindrical algebraic decomposition, 134-183, (1975)
[53] Wang D K, Mechanical proving of a group of space geometric theorem, Master Degree Thesis, Institute of Systems Science, CAS, Beijing, 1990.
[54] Wang, D. K., A mechanical solution to a group of space geometry problem, 236-243, (1992)
[55] Deakin, M. A B., A simple proof of the Beijing theorem, The Mathematical Gazette, 76, 251-254, (1992) · Zbl 0788.51018
[56] Nagasaka, K., Parametric greatest common divisors using comprehensive Gröbner systems, 341-348, (2017)
[57] Kapur, D.; Lu, D.; Monagan, M.; etal., An efficient algorithm for computing parametric multivariate polynomial GCD, 239-246, (2018)
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.