×

zbMATH — the first resource for mathematics

A survey on signature-based algorithms for computing Gröbner bases. (English) Zbl 1412.68306
Summary: In [Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal. Innsbruck: Universität Innsbruck (PhD Thesis) (1965)] B. Buchberger introduced an algorithmic approach to compute Gröbner bases. Later on, he and many others presented various attempts to improve the computation by removing useless elements a priori. One approach, initiated by Gebauer, Möller, Mora and Traverso in the 1990s, is to keep track of the corresponding syzygies which is related to the topic of this survey: signature-based algorithms for Gröbner bases. This area was initiated by J.-C. Faugère’s F5 algorithm [in: Proceedings of the 2002 international symposium on symbolic and algebraic computation, ISSAC’02. New York, NY: ACM Press. 75–83 (2002; Zbl 1072.68664)]. The general idea of signatures is to keep track of the history of the computation with a minimal overhead and to exploit this information to detect redundant elements. Here we give a summary of the literature on signature-based algorithms and show how to classify known algorithms by 3 different orderings. For this we give translations between different notations and show the relationships (differences and similarities) among many approaches. Moreover, we give a general description of how the idea of signatures is quite natural when performing the reduction process using linear algebra. We hope that this survey would help to outline this field of active research.

MSC:
68W30 Symbolic computation and algebraic computation
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
Software:
F5C; PoSSo; slimgb
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Albrecht, M.; Perry, J., F4/5, (2010)
[2] Arri, A.; Perry, J., The F5 criterion revised, J. Symb. Comput., 46, 2, 1017-1029, (June 2011), Preprint online at
[3] Ars, G., Applications des bases de Gröbner à la cryptographie, (2005), Université de Rennes I, PhD thesis
[4] Ars, G.; Hashemi, A., Extended F5 criteria, J. Symb. Comput., 45, 12, 1330-1340, (2010), MEGA 2009 special issue · Zbl 1218.13014
[5] Bardet, M., Étude des systèmes algébriques surdéterminés. applications aux codes correcteurs et à la cryptographie, (2004), Université Paris 6, PhD thesis
[6] Bardet, M.; Faugère, J.-C.; Salvy, B.; Yang, B. Y., Asymptotic expansion of the degree of regularity for semi-regular systems of equations, (The Effective Methods in Algebraic Geometry Conference, Mega 2005, (May 2005)), 1-14
[7] Becker, T.; Weispfenning, V.; Kredel, H., Gröbner bases - A computational approach to commutative algebra, Graduate Texts in Mathematics, (1993), Springer Verlag
[8] Bini, D. A.; Mourrain, B., Polynomial test suite, (2012)
[9] Brickenstein, M., Slimgb: Gröbner bases with slim polynomials, Rev. Mat. Complut., 23, 2, 453-466, (2010), the final publication is available at · Zbl 1200.13044
[10] Buchberger, B., Ein algorithmus zum auffinden der basiselemente des restklassenringes nach einem nulldimensionalen polynomideal, (1965), University of Innsbruck, PhD thesis · Zbl 1245.13020
[11] Buchberger, B., Ein algorithmisches kriterium für die Lösbarkeit eines algebraischen gleichungssystems, Aequ. Math., 4, 3, 374-383, (1970), English translation in: B. Buchberger, F. Winkler: Groebner Bases and Applications, Proc. of the International Conference “33 Years of Groebner Bases”, 1998, RISC, Austria, London Math. Society Lecture Note Series 251, Cambridge Univ. Press, 1998, pp. 535-545 · Zbl 0212.06401
[12] Buchberger, B., A criterion for detecting unnecessary reductions in the construction of Gröbner bases, (EUROSAM ’79: An International Symposium on Symbolic and Algebraic Manipulation, Lecture Notes in Computer Science, vol. 72, (1979), Springer), 3-21 · Zbl 0417.68029
[13] Buchberger, B., A critical-pair/completion algorithm for finitely generated ideals in rings, Lecture Notes in Computer Science, 171, 137-161, (1984) · Zbl 0546.68021
[14] Buchberger, B., Gröbner bases: an algorithmic method in polynomial ideal theory, (Bose, N. K., Multidimensional Systems Theory - Progress, Directions and Open Problems in Multidimensional Systems, (1985), D. Reidel Publication Company), 184-232 · Zbl 0587.13009
[15] Buchberger, B., History and basic features of the critical-pair/completion procedure, J. Symb. Comput., 3, 1/2, 3-38, (1987) · Zbl 0645.68094
[16] Buchberger, B., An algorithm for finding the basis elements of the residue class ring of zero dimensional polynomial ideal, J. Symb. Comput., 41, 3-4, 475-511, (2006), (English translation of Bruno Buchberger’s PhD thesis) · Zbl 1158.01307
[17] Cox, D. A.; Little, J.; O’Shea, D. B., Ideals, varieties, and algorithms, Undergraduate Texts in Mathematics, (2007), Springer
[18] Decker, Wolfram; Greuel, Gert-Martin; Pfister, Gerhard; Schönemann, Hans, \scsingular 4-0-2 - a computer algebra system for polynomial computations, (2015)
[19] Dellaca, R. D., Gröbner basis algorithms, (2009), California State University Fullerton, PhD thesis
[20] Eder, C., A new attempt on the F5 criterion, Comput. Sci. J. Mold., 16, 4-14, (2008) · Zbl 1162.68824
[21] Eder, C., On the criteria of the F5 algorithm, (2008), Preprint
[22] Eder, C., Signature-based algorithms to compute standard bases, (2012), University of Kaiserslautern Germany, PhD thesis
[23] Eder, C., An analysis of inhomogeneous signature-based Gröbner basis computations, J. Symb. Comput., 59, 21-35, (2013) · Zbl 1311.13037
[24] Eder, C., Improving incremental signature-based Groebner bases algorithms, ACM SIGSAM Commun. Comput. Algebra, 47, 1, 1-13, (2013) · Zbl 1322.68277
[25] Eder, C., Predicting zero reductions in Gröbner basis computations, (2014), Preprint at · Zbl 1346.13058
[26] Eder, C.; Gash, J.; Perry, J., Modifying faugère’s F5 algorithm to ensure termination, ACM SIGSAM Commun. Comput. Algebra, 45, 2, 70-89, (2011) · Zbl 1305.68353
[27] Eder, C.; Perry, J., F5C: a variant of faugère’s F5 algorithm with reduced Gröbner bases, J. Symb. Comput., 45, 12, 1442-1458, (2010), MEGA 2009 special issue · Zbl 1227.13018
[28] Eder, C.; Perry, J., Signature-based algorithms to compute Gröbner bases, (Proceedings of the 2011 International Symposium on Symbolic and Algebraic Computation, ISSAC 2011, (2011)), 99-106 · Zbl 1323.68593
[29] Eder, C.; Roune, B. H., Signature rewriting in Gröbner basis computation, (Proceedings of the 2013 International Symposium on Symbolic and Algebraic Computation, ISSAC 2013, (2013)), 331-338 · Zbl 1360.68929
[30] Faugère, J.-C., A new efficient algorithm for computing Gröbner bases (F4), J. Pure Appl. Algebra, 139, 61-88, (1999) · Zbl 0930.68174
[31] Faugère, J.-C., A new efficient algorithm for computing Gröbner bases without reduction to zero F5, (ISSAC’02, Villeneuve d’Ascq, France, (July 2002)), 75-82, Revised version from
[32] Faugère, J.-C.; Gianni, P. M.; 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
[33] Faugère, J.-C.; Joux, A., Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Gröbner bases, (CRYPTO 2003, Advances in Cryptology, vol. 2729, (2003)), 44-60 · Zbl 1122.94371
[34] Faugère, J.-C.; Safey El Din, M.; Spaenlehauer, P.-J., Gröbner bases of bihomogeneous ideals generated by polynomials of bidegree \((1, 1)\): algorithms and complexity, J. Symb. Comput., 46, 4, 106-437, (2011) · Zbl 1226.13017
[35] Faugère, J.-C.; Safey El Din, M.; Verron, T., On the complexity of computing Gröbner bases for quasi-homogeneous systems, (Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation, ISSAC ’13, (2013), ACM New York, NY, USA), 189-196 · Zbl 1360.68930
[36] Faugère, J.-C.; Svartz, J., Solving polynomial systems globally invariant under an action of the symmetric group and application to the equilibria of n vertices in the plane, (Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation, ISSAC ’12, (2012), ACM New York, NY, USA), 170-178 · Zbl 1323.68597
[37] Faugère, J.-C.; Svartz, J., Gröbner bases of ideals invariant under a commutative group: the non-modular case, (Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation, ISSAC ’13, (2013), ACM New York, NY, USA), 347-354 · Zbl 1360.68931
[38] Faugère, J.-C.; Lachartre, S., Parallel Gaussian elimination for Gröbner bases computations in finite fields, (Moreno-Maza, M.; Roch, J. L., Proceedings of the 4th International Workshop on Parallel and Symbolic Computation, PASCO ’10, (July 2010), ACM New York, NY, USA), 89-97
[39] Faugère, J.-C.; Rahmany, S., Solving systems of polynomial equations with symmetries using SAGBI-Gröbner bases, (Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation, ISSAC ’09, (2009), ACM New York, NY, USA), 151-158 · Zbl 1237.13052
[40] Galkin, V. V., Termination of original F5, (2012)
[41] Galkin, V. V., Simple signature based iterative algorithm for calculation of Gröbner bases, Mosc. Univ. Math. Bull., 68, 5, 231-236, (2013) · Zbl 1333.13035
[42] Galkin, V. V., Termination of the F5 algorithm, Program. Comput. Softw., 40, 47-57, (2014), (translation from Programmirovanie 40, No. 2, 2014) · Zbl 1323.68598
[43] Gao, S.; Guan, Y.; Volny IV, F., A new incremental algorithm for computing Gröbner bases, (Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation, ISSAC ’10, (2010), ACM), 13-19 · Zbl 1321.68531
[44] Gao, S.; Volny IV, F.; Wang, M., A new algorithm for computing Groebner bases, (2010)
[45] Gao, S., Volny IV, F., Wang, M., 2011. A new algorithm for computing Groebner bases (rev. 2011). http://www.math.clemson.edu/ sgao/papers/gvw.pdf.
[46] Gao, S., Volny IV, F., Wang, M., 2013. A new algorithm for computing Groebner bases (rev. 2013). http://www.math.clemson.edu/ sgao/papers/gvw_R130704.pdf.
[47] Gao, S.; Volny IV, F.; Wang, M., A new framework for computing Gröbner bases, Math. Comput., 85, 449-465, (2016) · Zbl 1331.13018
[48] Gash, J. M., On efficient computation of Gröbner bases, (2008), University of Indiana Bloomington, IN, PhD thesis
[49] Gash, J.M., 2009. A provably terminating and speed-competitive variant of F5 - F5t. Unpublished preprint.
[50] Gebauer, R.; Möller, H. M., Buchberger’s algorithm and staggered linear bases, (Proceedings of the Fifth ACM Symposium on Symbolic and Algebraic Computation, SYMSAC ’86, (1986), ACM New York, NY, USA), 218-221
[51] Gebauer, R.; Möller, H. M., On an installation of Buchberger’s algorithm, J. Symb. Comput., 6, 2-3, 275-286, (October/December 1988)
[52] Gerdt, V. P.; Hashemi, A., On the use of buchberger criteria in G2V algorithm for calculating Gröbner bases, Program. Comput. Softw., 39, 2, 81-90, (March 2013)
[53] Gerdt, V. P.; Hashemi, A.; Alizadeh, M. B., Involutive bases algorithm incorporating F5 criterion, J. Symb. Comput., 59, 1-20, (2013) · Zbl 1435.68391
[54] Greuel, G.-M.; Pfister, G., A \scsingular introduction to commutative algebra, (2007), Springer Verlag
[55] Huang, L., A new conception for computing Gröbner basis and its applications, (2010)
[56] Kandri-Rody, A.; Weispfenning, V., Non-commutative Gröbner bases in algebras of solvable type, J. Symb. Comput., 9, 1, 1-26, (1990) · Zbl 0715.16010
[57] Kapur, D.; Madlener, K., A completion procedure for computing a canonical basis for a k-subalgebra, Comput. Math., 1-11, (1989)
[58] Kollreider, C.; Buchberger, B., An improved algorithmic construction of Gröbner-bases for polynomial ideals, SIGSAM Bull., 12, 27-36, (May 1978)
[59] Kreuzer, M.; Robbiano, L., Computational commutative algebra 2, (2005), Springer Verlag · Zbl 1090.13021
[60] Kreuzer, M.; Robbiano, L., Computational commutative algebra 1, (2009), Springer Verlag
[61] Lazard, D., Gröbner bases, Gaussian elimination and resolution of systems of algebraic equations, (van Hulzen, J. A., European Computer Algebra Conference, EUROCAL’83, Springer LNCS, vol. 162, (1983)), 146-156 · Zbl 0539.13002
[62] Macaulay, F. S., On some formulæ in elimination, Proc. Lond. Math. Soc., 33, 1, 3-27, (1902) · JFM 34.0195.01
[63] Macaulay, F. S., The algebraic theory of modular systems, (1916), Cambridge University Press · JFM 46.0167.01
[64] Marinari, M. G.; Möller, H. M.; Mora, T., Gröbner bases of ideals defined by functionals with an application to ideals of projective points, Appl. Algebra Eng. Commun. Comput., 4, 103-145, (1993) · Zbl 0785.13009
[65] Möller, H. M.; Mora, T.; Traverso, C., Gröbner bases computation using syzygies, (ISSAC 92: Papers from the International Symposium on Symbolic and Algebraic Computation, (1992)), 320-328 · Zbl 0925.13010
[66] Mora, T., Solving polynomial equation systems II: Macaulay’s paradigm and Gröbner technology, Encyclopedia of Mathematics and its Applications, (2005), Cambridge University Press · Zbl 1161.13306
[67] Pan, S.; Hu, Y.; Wang, B., The termination of algorithms for computing Gröbner bases, (2012)
[68] Pan, S.; Hu, Y.; Wang, B., The termination of the F5 algorithm revisited, (Proceedings of the 2013 International Symposium on Symbolic and Algebraic Computation, ISSAC 2013, (2013)), 291-298 · Zbl 1360.68949
[69] Roune, B. H.; Stillman, M., Practical Gröbner basis computation, (Proceedings of the 2012 International Symposium on Symbolic and Algebraic Computation, ISSAC 2012, (2012)) · Zbl 1308.68185
[70] Roune, B. H.; Stillman, M., Practical Gröbner basis computation (extended version), (2012) · Zbl 1308.68185
[71] Stegers, T., Faugère’s F5 algorithm revisited, (2007), Technische Univerität Darmstadt, Master’s thesis
[72] Sun, Y., Signature-based Gröbner basis algorithms - extended MMM algorithm for computing Gröbner bases, (2013)
[73] Sun, Y.; Wang, D. K., A new proof for the correctness of the F5(F5-like) algorithm, (2010)
[74] Sun, Y.; Wang, D. K., A generalized criterion for signature related Gröbner basis algorithms, (Proceedings of the 2011 International Symposium on Symbolic and Algebraic Computation, ISSAC 2011, (2011)), 337-344 · Zbl 1323.68630
[75] Sun, Y.; Wang, D. K., The F5 algorithm in Buchberger’s style, J. Syst. Sci. Complex., 24, 6, 1218-1231, (2011) · Zbl 1339.68322
[76] Sun, Y.; Wang, D. K., A new proof for the correctness of the F5 algorithm, Sci. China Math., 56, 4, 745-756, (2013) · Zbl 1286.13026
[77] Sun, Y.; Wang, D. K., Extending the GVW algorithm to compute Gröbner bases, Sci. China Math., (2013), Submitted for publication
[78] Sun, Y.; Wang, D. K.; Huang, Z.; Lin, D., A monomial-oriented GVW for computing Gröbner bases, (2014)
[79] Sun, Y.; Wang, D. K.; Ma, D. X.; Zhang, Y., A signature-based algorithm for computing Gröbner bases in solvable polynomial algebras, (Proceedings of the 2011 International Symposium on Symbolic and Algebraic Computation, ISSAC 2012, (2012)), 351-358 · Zbl 1308.68193
[80] Thiéry, Nicolas M., Computing minimal generating sets of invariant rings of permutation groups with SAGBI-Gröbner basis, (DM-CCG, (2001)), 315-328 · Zbl 1017.68149
[81] Traverso, C., Gröbner trace algorithms, (ISSAC’88, (1988))
[82] Volny, F., New algorithms for computing Gröbner bases, (2011), Clemson University, PhD thesis
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.