zbMATH — the first resource for mathematics

Gröbner systems conversion. (English) Zbl 1409.68344
Summary: In this paper, we consider the problem of converting parametric Gröbner bases. More precisely, given a (comprehensive) Gröbner system w.r.t. a given monomial ordering, we present an efficient method to convert this system into a Gröbner system w.r.t. another monomial ordering. For this purpose, we develop the parametric variant of the generic Gröbner walk algorithm due to Fukuda et al. This new algorithm takes as input a monomial ordering and a Gröbner basis w.r.t. a set of parametric constraints, and outputs a decomposition of the given space of parameters as a finite set of (parametric) cells and for each cell a Gröbner basis w.r.t. the target monomial ordering.

68W30 Symbolic computation and algebraic computation
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
Full Text: DOI
[1] Adams, W.W., Loustaunau, P.: An Introduction to Gröbner Bases. American Mathematical Society, Providence (1994) · Zbl 0803.13015
[2] Amrhein, B., Gloor, O.: The fractal walk. In: Gröbner Bases and Applications. Based on a Course for Young Researchers, pp. 305–322. Cambridge University Press, Cambridge (1998) · Zbl 0937.13007
[3] Becker, T., Weispfenning, V.: Gröbner bases: a computational approach to commutative algebra. In: Cooperation with Heinz Kredel. Springer, New York (1993) · Zbl 0772.13010
[4] Bosma, W., Cannon, J., Playoust, C.: The Magma algebra system. I: the user language. J. Symb. Comput. 24(3–4), 235–265 (1997) · Zbl 0898.68039
[5] Buchberger, B.: A criterion for detecting unnecessary reductions in the construction of Gröbner-bases. In: Symbolic and Algebraic Computation, EUROSAM ’79, Lect. Notes Comput. Sci., vol. 72, pp. 3–21 (1979) · Zbl 0417.68029
[6] Buchberger, B.: Bruno Buchberger’s Ph.D. thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal. Translation from the German. J. Symb. Comput. 41(3–4), 475–511 (2006) · Zbl 1158.01307
[7] Collart, S., Kalkbrener, M., Mall, D.: Converting bases with the Gröbner walk. J. Symb. Comput. 24(3–4), 465–469 (1997) · Zbl 0908.13020
[8] Cox, D., Little, J., O’Shea, D.: Ideals, Varieties, and Algorithms. An Introduction to Computational Algebraic Geometry and Commutative Algebra, 3rd edn. Springer, New York (2007) · Zbl 1118.13001
[9] Cox, D.A.: Gröbner bases tutorial, Part II: a sampler of recent developments. ISSAC’07. http://dacox.people.amherst.edu/lectures/gb2.handout (2007)
[10] Cox, D.A., Little, J., O’Shea, D.: Using Algebraic Geometry, 2nd edn. Springer, New York (2005)
[11] Dehghani Darmian, M., Hashemi, A.: Parametric FGLM algorithm. J. Symb. Comput. (2017). doi: 10.1016/j.jsc.2016.12.006 · Zbl 1359.13030
[12] Dehghani Darmian, M., Hashemi, A., Montes, A.: Erratum to ”A new algorithm for discussing Gröbner bases with parameters”. J. Symb. Comput. 33 (1–2) (2002) 183–208]. J. Symb. Comput. 46(10), 1187–1188 (2011) · Zbl 1279.13037
[13] Faugère, J., Gianni, P., Lazard, D., Mora, T.: Efficient computation of zero-dimensional Gröbner bases by change of ordering. J. Symb. Comput. 16(4), 329–344 (1993) · Zbl 0805.13007
[14] Fukuda, K., Jensen, A., Lauritzen, N., Thomas, R.: The generic Gröbner walk. J. Symb. Comput. 42(3), 298–312 (2007) · Zbl 1124.68120
[15] Fukuda, K., Jensen, A.N., Thomas, R.R.: Computing Gröbner fans. Math. Comput. 76(260), 2189–2212 (2007) · Zbl 1119.13026
[16] Hashemi, A., M.-Alizadeh, B., Dehghani Darmian, M.: Minimal polynomial systems for parametric matrices. Linear Multilinear Algebra 61(2), 265–272 (2013) · Zbl 1261.15014
[17] Kalkbrener, M.: On the complexity of Gröbner bases conversion. J. Symb. Comput. 28(1–2), 265–273 (1999) · Zbl 0939.68170
[18] Kapur, D.: An approach for solving systems of parametric polynomial equations. In: Saraswat, V., Van Hentenryck, P. (eds.) Principles and Practice of Constraint Programming, pp. 217–224. MIT Press, Cambridge (1995)
[19] Kapur, D., Sun, Y., Wang, D.: A new algorithm for computing comprehensive Gröbner systems. In: Proceedings of ISSAC’10, pp. 29–36. ACM Press (2010) · Zbl 1321.68533
[20] Kapur, D., Sun, Y., Wang, D.: Computing comprehensive Gröbner systems and comprehensive Gröbner bases simultaneously. In: Proceedings of ISSAC’11, pp. 193–200. ACM Press (2011) · Zbl 1323.13004
[21] 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
[22] Kapur, D., Sun, Y., Wang, D.: An efficient method for computing comprehensive Gröbner bases. J. Symb. Comput. 52, 124–142 (2013) · Zbl 1283.13024
[23] Kapur, D., Sun, Y., Wang, D., Zhou, J.: Computations in residue class rings of (parametric) polynomial ideals. http://www.amss.ac.cn/xwdt/kydt/201304/P020130407398997830230 (2016)
[24] Manubens, M., Montes, A.: Improving the DISPGB algorithm using the discriminant ideal. J. Symb. Comput. 41(11), 1245–1263 (2006) · Zbl 1121.13031
[25] Manubens, M., Montes, A.: Minimal canonical comprehensive Gröbner systems. J. Symb. Comput. 44(5), 463–478 (2009) · Zbl 1159.13304
[26] Montes, A.: A new algorithm for discussing Gröbner bases with parameters. J. Symb. Comput. 33(2), 183–208 (2002) · Zbl 1068.13016
[27] Montes, A., Castro, J.: Solving the load flow problem using the Gröbner basis. SIGSAM Bull. 29(1), 1–13 (1995) · Zbl 1097.90509
[28] Montes, A., Schönemann, H.: Singular ”grobcov.lib” library D.2.4. http://www.singular.uni-kl.de (2016). Computer Algebra System for polynomial computations. Center for Computer Algebra, University of Kaiserslautern, free software under the GNU General Public Licence, last release 4-1-0 (2016)
[29] Montes, A., Wibmer, M.: Gröbner bases for polynomial systems with parameters. J. Symb. Comput. 45(12), 1391–1425 (2010) · Zbl 1207.13018
[30] Mora, T., Robbiano, L.: The Gröbner fan of an ideal. J. Symb. Comput. 6(2–3), 183–208 (1988) · Zbl 0668.13017
[31] Robbiano, L.: Term orderings on the polynomial ring. Computer algebra. In: EUROCAL’85, Lect. Notes Comput. Sci., vol. 204, pp. 513–517 (1985)
[32] Sato, Y., Suzuki, A.: Computation of inverses in residue class rings of parametric polynomial ideals. In: Proceedings of ISSAC’09, pp. 311–315. ACM Press (2009) · Zbl 1237.13040
[33] Sturmfels, B.: Gröbner Bases and Convex Polytopes. AMS, American Mathematical Society, Providece (1996) · Zbl 0856.13020
[34] Suzuki, A., Sato, Y.: An alternative approach to comprehensive Gröbner bases. J. Symb. Comput. 36(3–4), 649–667 (2003) · Zbl 1053.13013
[35] Suzuki, A., Sato, Y.: A simple algorithm to compute comprehensive Gröbner bases using Gröbner bases. In: Proceedings of ISSAC’06, pp. 326–331. ACM Press (2006) · Zbl 1356.13040
[36] Tran, Q.-N.: A fast algorithm for Gröbner basis conversion and its applications. J. Symb. Comput. 30(4), 451–467 (2000) · Zbl 0988.13016
[37] Weispfenning, V.: Comprehensive Gröbner bases. J. Symb. Comput. 14(1), 1–29 (1992) · Zbl 0784.13013
[38] Weispfenning, V.: Canonical comprehensive Gröbner bases. J. Symb. Comput. 36(3–4), 669–683 (2003) · Zbl 1054.13015
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.