Seminar: Topics in Gröbner Bases [Summer 2016]
Michael Joswig, Institut für Mathematik, TU Berlin.
Description
Gröbner bases are special generating systems of ideals in polynomial rings which have good algorithmic properties. For this reason computing Gröbner bases is a fundamental algorithmic task which is at the core of many techniques in computer algebra and its applications. The seminar covers topics in commutative algebra, algebraic and polyhedral geometry, optimization, algorithms and more.
The seminar is organized in blocks with talks given by the participants. Usually each talk is about one scientific original paper. The presentations will take place on Tuesdays May 3rd, May 24th, June 7th and June 14th respectively from 9:30 till 13:00.
First Meeting: Wednesday, April 20, 14:00 in room: MA 621. This is mandatory for all participants.
Q+A Meeting: Tuesday, May 3, 10:00 in room: MA 621.
This meeting offers the possiblity to ask questions about the presentation and your specific topic.
The talks will be given on Tuesday, May 24 and June 7.
List of possible Presentations
The order of the presentations is fixed. The dates will be assigned. Please sign in for the presentation of your choice at the office MA 6 - 2 in MA 625. (If the topic of your choice is already taken by someone else you will have to choose another topic.)
Presentations for Bachelor Students
- Joswig and Theobald: Polyhedral and Algebraic Methods in Computational Geometry. § 9.4 - 9.6 (Buchberger Algorithm)
- Joswig and Theobald: Polyhedral and Algebraic Methods in Computational Geometry. § 8.3 + 10.1 + 10.2 (Resultants)
- Joswig and Theobald: Polyhedral and Algebraic Methods in Computational Geometry. § 10.3 - 10.5 (Elimination)
- Joswig and Theobald: Polyhedral and Algebraic Methods in Computational Geometry. § 10.6 (Conti-Traverso Method)
- Cox, Little and O'Shea: Ideals, Varieties and Algorithms. § 4.2 + 4.3 (Radical ideals)
- Cox, Little and O'Shea: Ideals, Varieties and Algorithms. § 4.4 + 4.5 (Zariski closure)
Presentations for Bachelor or Master Students
- Sturmfels: Gröbner Bases and Convex Polytopes. Chap. 2 (State Polytope)
- Sturmfels: Gröbner Bases and Convex Polytopes. Chap. 3 (Variation of Term Orders)
Presentations for Master Students
- Maclagan and Sturmfels: Introduction to Tropical Geometry. § 2.4 (Gröbner bases over fields with valuation)
- Maclagan and Sturmfels: Introduction to Tropical Geometry. § 2.5 (Gröbner complexes)
- Boroujeni, Basiri, Rahmany, Valibouze: F4-invariant algorithm for computing SAGBI-Gröbner bases. Theoret. Comput. Sci. 573 (2015), 54-62.
- Gao, Volny and Wang: A new framework for computing Gröbner bases. Math. Comp. 85 (2016), no. 297, 449-465.
- Knuth and Bendix: Simple Word Problems in Universal Algebra. In Computational Problems in Abstract Algebra (Proc. Conf., Oxford, 1967). Pergamon Press, pp. 263-297, 1970.
- Mayr and Meyer. The complexity of the word problems for commutative semigroups and polynomial ideals. Adv. in Math., 46(3):305-329, 1982.
Dates of the Presentations
Tuesday, May 24th
| 09:30 | Susanne Biebler | Joswig and Theobald: Polyhedral and Algebraic Methods in Computational Geometry. § 9.4 - 9.6 (Buchberger Algorithm) |
| 10:30 | Michael Joswig | Joswig and Theobald: Polyhedral and Algebraic Methods in Computational Geometry. § 10.3 - 10.5 (Elimination) |
| 11:30 | Mirco Malik | Cox, Little and O'Shea: Ideals, Varieties and Algorithms. § 4.2 + 4.3 (Radical ideals) |
Tuesday, June 7th
| 09:30 | Marie Sophie Eisenhardt | Knuth and Bendix: Simple Word Problems in Universal Algebra. In Computational Problems in Abstract Algebra |
| 10:30 | Sybille Meyer | Mayr and Meyer. The complexity of the word problems for commutative semigroups and polynomial ideals. |
| 11:30 | Constantin Fischer | Maclagan and Sturmfels: Introduction to Tropical Geometry. § 2.4 (Gröbner bases over fields with valuation) |
Hints concerning the presentation
- The presentation should take between 45 and 60 minutes and can be given either in German or in English. The talk is directed to the other participants and students of the seminar. They have a similar basic background as yourself.
- It is almost sure that there is not enough time to present all details of your specific topic. Therefore you have to choose and to decide what is important and what is not. You have to present one full proof at least. If this seems to be too difficult in your case it is allowed to restrict to a special case or to a part of the proof.
- You are free to choose between a beamer or blackboard presentation. It is possible to combine both; but take into account that this means an additional organizational effort during the talk and therefore makes the realization more complicated. Therefore, I recommend to do so only in exceptional cases and after a very careful preparation.
- A comment on the overall preparation: About the same amount of time you need to digest the topic you will additionally need to 'construct' your presentation.
- It is not necessary to prepare a written elaboration.
References (basic)
- Cox, Little and O'Shea: Ideals, varieties and algorithms. UTM. Springer, 2015. ISBN: 978-3-319-16721-3.
- Cox, Little and O'Shea: Using algebraic geometry. Second edition. GTM. Springer, 2005. ISBN: 0-387-20706-6.
- Joswig and Theobald: Polyhedral and Algebraic Methods in Computational Geometry. Springer, 2013. ISBN: 978-1-4471-4817-3.
- Sturmfels: Gröbner bases and convex polytopes. University Lecture Series. AMS, Providence, RI, 1996. ISBN: 0-8218-0487-1.
The sections 9.1, 9.2 and 9.3 in [3] are mandatory reading for all participants of the seminar.
This literature is available in the library of the Department of Mathematics.
References (advanced)
- Boroujeni, Basiri, Rahmany and Valibouze: F4-invariant algorithm for computing SAGBI-Gröbner bases. Theoret. Comput. Sci. 573 (2015), 54-62.
- Gao, Volny and Wang: A new framework for computing Gröbner bases. Math. Comp. 85 (2016), no. 297, 449-465.
- Knuth and Bendix: Simple word problems in universal algebras. Pergamon, Oxford, 1967.
- Mayr and Meyer. The complexity of the word problems for commutative semigroups and polynomial ideals. Adv. in Math., 46(3):305-329, 1982.
References (background)
- Buchberger: A theoretical basis for the reduction of polynomials to canonical forms. ACM SIGSAM Bulletin, 1976. DOI: 10.1145/1088216.1088219.
- Faugère: A new efficient algorithm for computing Gröbner bases (F4). J. Pure Appl. Algebra 139 (1999), no. 1-3, 61-88.
- Faugère: A new efficient algorithm for computing Gröbner bases without reduction to zero (F5). Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, 75-83 (electronic), ACM, New York, 2002.
- von zur Gathen and Gerhard: Modern computer algebra. Third edition. Cambridge University Press, 2013. ISBN: 978-1-107-03903-2.
- Hironaka: Resolution of singularities of an algebraic variety over a field of characteristic zero. Annals of Mathematics, 1964. DOI: 10.2307/1970486.
- Maclagan and Sturmfels: Introduction to tropical geometry. AMS 2015.