Comparing complexities of problems of determining of Grebner’s basis of ideal and solving this ideal
Abstract
A new method of investigation of ideals in the rings of polynomials was proposed by B. Buchberger in 1965. He proposed to use special basis in such rings named “Gröbner Basis” in the honor of his teacher. The proposed approach has allowed to prove the algorithmic reducibility of the task of finding solutions of a system of algebraic equations in many variables to the problem of solving algebraic equation of one variable. However, the practical use of the method needs enormous computational cost. The first estimate of the computational complexity of this method was obtained by G. Hermann in 1925, when the concept of Gröbner basis was not yet known. Was obtained the required upper estimate in the form of dual exponent of the number of variables and the maximum degree of incoming task description polynomials of degree of decomposition element ideal for an arbitrary basis. As it turned out later by T.W. Dube this estimate cannot be improved.
In 1996 K. Kühnle and E. W. Mayr proved, that for Boolean ideals the upper bound of memory capacity is exponential on input size. For zero-dimensional ideals A. Hashemi and D. Lazard proved the exponential complexity of finding Gröbner basis. Here we prove the lower bound of computation of such bases, by giving an example of an ideal having Gröbner basis of exponential size on input.References
1. [Bar04] Bardet, M. and Faugere, J.C and Salvy, B. “On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations”.In: International Conference on Polynomial System Solving - ICPSS. Paris, France, Nov. 2004, pp. 71 –75.
2. [Bro87] D. Brownawell. “Bounds for the degrees in the Nullstellensatz”. In: Annals of Math. Second Series 126.3 (1987), pp. 577–591.
3. [Buc06] B. Buchberger. Ein Algorithmus zum Auffinden der Basiselemente des Restklassenrings nach einem nulldimensionalen Polynomideal (An Algorithm for Finding the Basis Elements in the Residue Class Ring Modulo a Zero Dimensional Polynomial Ideal). PhD thesis, Universität Innsbruck, 1965. English translation in J. of Symbolic Computation, Special Issue on Logic, Mathematics, and Computer Science: Interactions. 41(3/4):475--511, 2006.
4. [Buc01 ] B. Buchberger. Gröbner Bases : A Short Introduction for Systems Theorists, Computer Aided Systems Theory—EUROCAST 2001 (2001) Volume: 330, Issue: 9, Publisher: Springer, Pages: 1–19.
5. [Gio52] Trevisan Giorgio. “Classificazione dei semplici ordinamenti di un gruppo libero commutativo con n generatori”. In: vol. 22. CEDAM, 1952, pp. 143–156.
6. [Giu84] Marc Giusti.“Some Effectivity Problems in Polynomial Ideal Theory”. In: Proceedings of the International Symposium on Symbolic and Algebraic Computation. EUROSAM’84. London, UK: Springer-Verlag, 1984, pp. 159–171.
7. [Fau02] J.-C. Faugere. “A new efficient algorithm for computing Gröbner bases without reduction to zero (F5)”. In: Proceedings of the 2002 international symposium on Symbolic and algebraic computation. ISSAC ’02. Lille, France: ACM, 2002, pp. 75–83.
8. [Fau99] J.-C. Faugere. “A new efficient algorithm for computing Gröbner bases (F4).” In: Journal of Pure and Applied Algebra 139. 1–3(June 1999), pp. 61–88.
9. [Her25] G. Hermann. Die Frage der endlich vielen Schritte in der Theorie der Polynomideale: Unt. Benutzung nachgelassener Satze v .Kurt Hentzelt. Springer, 1925.
10. [HL11] Amir Hashemi and Daniel Lazard. “Sharper Complexity Bounds for Zero-Dimensional Gröbner Bases and Polynomial System Solving”. In: IJAC 21.5 (2011), pp. 703–713.
11. [KM96] Klaus Kühnle and Ernst W. Mayr. “Exponential space computation of Gröbner bases”. In: Proceedings of the 1996 international symposium on Symbolic and algebraic computation. ISSAC’96. Zurich, Switzerland: ACM, 1996, pp. 63–71.
12. [Laz83] Daniel Lazard. “Gröbner-Bases, Gaussian elimination and resolution of systems of algebraic equations”. In: Proceedings of the European Computer Algebra Conference on Computer Algebra. London, UK: Springer-Verlag, 1983, pp. 146–156.
13. [May89] Ernst W. Mayr. “Membership in Polynomial Ideals over Q Is Exponential Space Complete”. In: STACS. Ed. by Burkhard Monien and Robert Cori. Vol. 349. Lecture Notes in Computer Science. Springer, 1989, pp. 400–406.
14. [May97] Ernst W. Mayr. “Some Complexity Results for Polynomial Ideals”. In: J. Complexity 13.3 (1997), pp. 303–325.
15. [MM82] E. Mayr and A. Meyer. “The complexity of the word problems for commutative semigroups and polynomial ideals”.English.In:Adv.Math., Beijing 46.3 (Dec. 1982), pp. 305–329.
16. [Riq10] C. Riquier. Les systèmes d’équations aux dérivées partielles. Cornell University Library historical math monographs. Gauthier-Villars, 1910.
17. [Rob85] Lorenzo Robbiano. Term orderings on the polynomial ring. Computer algebra, EUROCAL ’85, Proc. Eur. Conf., Linz/Austria 1985, Vol. 2, Lect. Notes Comput. Sci. 204, 513-517 (1985). 1985.
18. [МИ53] Зайцева М.И.. “О совокупности упорядочений абелевой группы”. Успехи математических наук 8 (1953), pp. 135–137.
19. [Dube] T. W. Dube, The structure of polynomial ideals and Grobner bases, SIAM Jornal of Computing, 19: 750-773, 1990.
Review
For citations:
Shokurov A.V. Comparing complexities of problems of determining of Grebner’s basis of ideal and solving this ideal. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2012;22. (In Russ.)
Email this article 