×

On the complexity of the \(F_5\) Gröbner basis algorithm. (English) Zbl 1328.68319

Summary: We study the complexity of Gröbner bases computation, in particular in the generic situation where the variables are in simultaneous Noether position with respect to the system.
We give a bound on the number of polynomials of degree \(d\) in a Gröbner basis computed by the second author’s \(F_5\) algorithm [in: Proceedings of the 2002 international symposium on symbolic and algebraic computation, ISSAC 2002. New York, NY: ACM Press. 75–83 (2002; Zbl 1072.68664)] in this generic case for the grevlex ordering (which is also a bound on the number of polynomials for a reduced Gröbner basis, independently of the algorithm used). Next, we analyse more precisely the structure of the polynomials in the Gröbner bases with signatures that \(F_5\) computes and use it to bound the complexity of the algorithm.
Our estimates show that the version of \(F_5\) we analyse, which uses only standard Gaussian elimination techniques, outperforms row reduction of the Macaulay matrix with the best known algorithms for moderate degrees, and even for degrees up to the thousands if Strassen’s multiplication is used. The degree being fixed, the factor of improvement grows exponentially with the number of variables.

MSC:

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

Citations:

Zbl 1072.68664
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] (Abramowitz, M.; Stegun, I. A., Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables (1992), Dover Publications Inc.: Dover Publications Inc. New York), reprint of the 1972 edition · Zbl 0543.33001
[2] Bardet, M., Étude des systèmes algébriques surdéterminés. Applications aux codes correcteurs et à la cryptographie (December 2004), Université Paris VI, PhD thesis
[3] Buchberger, B., Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal (1965), University of Innsbruck: University of Innsbruck Austria, PhD thesis · Zbl 1245.13020
[4] Coppersmith, D.; Winograd, S., Matrix multiplication via arithmetic progressions, J. Symb. Comput., 9, 3, 251-280 (Mar. 1990)
[5] Cox, D.; Little, J.; O’Shea, D., Ideals, Varieties, and Algorithms (1997), Springer-Verlag: Springer-Verlag New York
[6] Cox, D. A.; Little, J.; O’Shea, D., Using Algebraic Geometry, Graduate Texts in Mathematics, vol. 185 (2005), Springer · Zbl 1079.13017
[7] Dubé, T. W., The structure of polynomials ideals and Gröbner bases, SIAM J. Comput., 19, 4, 750-773 (Aug. 1990)
[8] Eder, C.; Faugère, J.-C., A survey on signature-based Gröbner basis computations (Apr. 2014)
[9] Eder, C.; Gash, J.; Perry, J., Modifying Faugère’s \(F_5\) algorithm to ensure termination, ACM Commun. Comput. Algebra, 45, 70-89 (July 2011)
[10] Faugère, J.-C., A new efficient algorithm for computing Gröbner bases \((F_4)\), J. Pure Appl. Algebra, 139, 1-3, 61-88 (1999) · Zbl 0930.68174
[11] Faugère, J.-C., A new efficient algorithm for computing Gröbner bases without reduction to zero \((F_5)\), (Mora, T., ISSAC 2002. Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation. ISSAC 2002. Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, Université de Lille, July 7-10, 2002 (2002), ACM Press: ACM Press France), 75-83 · Zbl 1072.68664
[12] Faugère, J.-C., FGb: a library for computing Gröbner bases, (Fukuda, K.; Hoeven, J.; Joswig, M.; Takayama, N., Mathematical Software - ICMS 2010. Mathematical Software - ICMS 2010, Lecture Notes in Computer Science, vol. 6327 (September 2010), Springer: Springer Berlin/Heidelberg), 84-87 · Zbl 1294.68156
[13] Faugère, J.-C.; Joux, A., Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Gröbner bases, (Boneh, D., Crypto’2003. Crypto’2003, Lecture Notes in Computer Science, vol. 2729 (2003), Springer-Verlag), 44-60 · Zbl 1122.94371
[14] Faugère, J.-C.; Rahmany, S., Solving systems of polynomial equations with symmetries using SAGBI-Gröbner bases, (Kaltofen, E., ISSAC ’09: Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation. ISSAC ’09: Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation, Seoul, Korea (2009), ACM), 151-158 · Zbl 1237.13052
[15] Faugère, J. C.; 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
[16] Gérard, R.; Jurkat, W. B., Asymptotic implicit function theorems. Part I: The preparation theorem and division theorem, Asymptot. Anal., 6, 45-71 (1992) · Zbl 0789.32005
[17] Giusti, M., Some effectivity problems in polynomial ideal theory, (Eurosam 84. Eurosam 84, Lecture Notes in Computer Science, vol. 174 (1984), Springer: Springer Berlin), 159-171 · Zbl 0585.13010
[18] Giusti, M., A note on the complexity of constructing standard bases, (Eurocal’85. Eurocal’85, Lecture Notes in Computer Science, vol. 204 (1985), Springer-Verlag), 411-412
[19] Giusti, M., Combinatorial dimension theory of algebraic varieties, Special Issue on Computational Aspects of Commutative Algebra. Special Issue on Computational Aspects of Commutative Algebra, J. Symb. Comput., 6, 2-3, 249-265 (1988) · Zbl 0697.14001
[20] Giusti, M.; Heintz, J., La détermination des points isolés et de la dimension d’une variété algébrique peut se faire en temps polynomial, (Computational Algebraic Geometry and Commutative Algebra. Computational Algebraic Geometry and Commutative Algebra, Cortona, 1991. Computational Algebraic Geometry and Commutative Algebra. Computational Algebraic Geometry and Commutative Algebra, Cortona, 1991, Symp. Math., vol. XXXIV (1993), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 216-256 · Zbl 0829.14029
[21] Giusti, M.; Hägele, K.; Lecerf, G.; Marchand, J.; Salvy, B., Computing the dimension of a projective variety: the projective Noether Maple package, J. Symb. Comput., 30, 3, 291-307 (Sep. 2000)
[22] Giusti, M.; Lecerf, G.; Salvy, B., A Gröbner free alternative for polynomial system solving, J. Complex., 17, 1, 154-211 (Mar. 2001)
[23] Hashemi, A.; Lazard, D., Sharper complexity bounds for zero-dimensional Gröbner bases and polynomial system solving, Int. J. Algebra Comput., 21, 5, 703-713 (2011) · Zbl 1228.13026
[24] Huỳnh, D. T., A superexponential lower bound for Gröbner bases and Church-Rosser commutative Thue systems, Inf. Control, 68, 1-3, 196-206 (1986) · Zbl 0612.68033
[25] Krick, T.; Pardo, L. M., A computational method for Diophantine approximation, (Algorithms in Algebraic Geometry and Applications. Algorithms in Algebraic Geometry and Applications, Santander, 1994. Algorithms in Algebraic Geometry and Applications. Algorithms in Algebraic Geometry and Applications, Santander, 1994, Progress in Mathematics, vol. 143 (1996), Birkhäuser: Birkhäuser Basel), 193-253 · Zbl 0878.11043
[26] Lakshman, Y. N., A single exponential bound on the complexity of computing Gröbner bases of zero-dimensional ideals, (Effective Methods in Algebraic Geometry. Effective Methods in Algebraic Geometry, Castiglioncello, 1990. Effective Methods in Algebraic Geometry. Effective Methods in Algebraic Geometry, Castiglioncello, 1990, Progress in Mathematics, vol. 94 (1991), Birkhäuser Boston: Birkhäuser Boston Boston, MA), 227-234
[27] Lakshman, Y. N.; Lazard, D., On the complexity of zero-dimensional algebraic systems, (Effective Methods in Algebraic Geometry. Effective Methods in Algebraic Geometry, Castiglioncello, 1990. Effective Methods in Algebraic Geometry. Effective Methods in Algebraic Geometry, Castiglioncello, 1990, Progress in Mathematics, vol. 94 (1991), Birkhäuser Boston: Birkhäuser Boston Boston, MA), 217-225
[28] Lazard, D., Gröbner bases, Gaussian elimination and resolution of systems of algebraic equations, (Computer Algebra. Computer Algebra, Proceedings Eurocal’83, London, 1983. Computer Algebra. Computer Algebra, Proceedings Eurocal’83, London, 1983, Lecture Notes in Computer Science, vol. 162 (1983), Springer: Springer Berlin), 146-156 · Zbl 0539.13002
[29] Le Gall, F., Powers of tensors and fast matrix multiplication, (ISSAC ’14 (2014)) · Zbl 1325.65061
[31] Macaulay, F. S., On some formulæ in elimination, Proc. Lond. Math. Soc., 33, 1, 3-27 (1902) · JFM 34.0195.01
[32] Macaulay, F. S., The Algebraic Theory of Modular Systems, Cambridge Mathematical Library (1916), Cambridge University Press: Cambridge University Press Cambridge, revised reprint edition in 1994 · Zbl 0802.13001
[33] Mayr, E. W.; Meyer, A. R., The complexity of the word problems for commutative semigroups and polynomial ideals, Adv. Math., 46, 3, 305-329 (1982) · Zbl 0506.03007
[34] Möller, H. M.; Mora, F., Upper and lower bounds for the degree of Groebner bases, (Eurosam 84. Eurosam 84, Lecture Notes in Computer Science, vol. 174 (1984), Springer: Springer Berlin), 172-183
[35] Stanley, R. P., Log-concave and unimodal sequences in algebra, combinatorics, and geometry, (Graph Theory and its Applications: East and West. Graph Theory and its Applications: East and West, Jinan, 1986. Graph Theory and its Applications: East and West. Graph Theory and its Applications: East and West, Jinan, 1986, Annals of the New York Academy of Sciences, vol. 576 (1989), New York Academy of Sciences: New York Academy of Sciences New York), 500-535 · Zbl 0792.05008
[36] Storjohann, A., Algorithms for matrix canonical forms (2000), Department of Computer Science, ETH: Department of Computer Science, ETH Zürich, PhD thesis
[37] Stothers, A., On the complexity of matrix multiplication (2010), University of Edinburgh, PhD thesis
[38] Vassilevska Williams, V., Multiplying matrices faster than Coppersmith-Winograd, (STOC’12—Proceedings of the 2012 ACM Symposium on Theory of Computing (2012), ACM: ACM New York), 887-898 · Zbl 1286.65056
[39] von zur Gathen, J.; Gerhard, J., Modern Computer Algebra (2003), Cambridge University Press: Cambridge University Press New York · Zbl 1055.68168
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.