Сравнение сложностей задач нахождения базиса Гребнера идеала и решений этого идеала
Аннотация
Сравниваются сложности задач нахождения решения системы алгебраических уравнений и базисов Гребнера идеалов этих систем.
Список литературы
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.
Рецензия
Для цитирования:
Шокуров А.В. Сравнение сложностей задач нахождения базиса Гребнера идеала и решений этого идеала. Труды Института системного программирования РАН. 2012;22.
For citation:
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.)
Послать статью по эл. почте 