Inhalt des Dokuments
zur Navigation
Description of the seminar
Modern algebraic geometry has developed a deep and far reaching theory to understand the zero sets of polynomial equations. Today's immense computational power brought the challenge of transfering the wisdom of algebraic geometry into working algorithms. In this seminar, we strive to prove theorems that can be communicated to computers. In other words, we develop effective methods in algebraic geometry.
In order to solve computational problems in algebraic geometry, there are usually two kinds of methods: symbolic and numerical. On the one hand, symbolic algorithms are always guaranteed to work, can be proven to halt in finitely many steps, but usually suffer from high computational complexity; on the other hand, numerical methods don't always work, are not guaranteed to halt in finitely many steps, but are provably fast for generic inputs. It is said that hybrid numeric-symbolic approaches are marriage made in heaven. However, it still remains a challenge today to combine symbolic and numerical approaches in computational algebraic geometry.
In this seminar, we will learn about both the symbolic and numerical methods, with particular emphasis on Gröbner basis, resultants, and Kaltofen's algorithm on the symbolic side; Newton's method, Smale's alpha theory, and homotopy continuation methods on the numerical side.
Schedule and plan
The seminar will take place on Thursdays from 16:15 to 17:45 at room MA316 of Technische Universität Berlin. The first session will be to distribute the topics among the attending students (i.e. eine Besprechung) and it will take place on the 18th of April, the talks of the seminar will start from the 2nd of May. If attending students request it, the time scheduled for the seminar could be changed for a suitable time for everyone.
Students should meet with Dr. Alperen Ergür and/or Josué Tonelli-Cueto the week before the talk to discuss the plan of their presentation.
Topic | Day | Speaker |
---|---|---|
Introduction and repartition of topics | 18/04 | |
Gröbner basis I | 03/05 | Kathlén Kohn |
Gröbner basis II | 17/05 | Florian Blatt |
Resultants | 24/05 | Mario Kummer |
Algorithms in Algebra and PIT I | 31/05 | Josué Tonelli-Cueto |
Algorithms in Algebra and PIT II | 14/06 | Alperen Ergür |
Algorithms in Algebra and PIT III | 28/06 | Sascha Timme |
Newton's method: Smale's alpha theory | 05/07 | Oğuzhan Yürük |
Homotopy Continuation I | 05/07 | Henning Seidler |
Geometric Framework for Condition | 12/07 | Levent Doğan |
Homotopy Continuation III | 19/07 | Peter Bürgisser |
Syllabus and description of topics
You can access an updated version the syllabus and description of the talks of the seminar in this overleaf document. A PDF document can also be downloaded in this link, but it may be not updated.
Literature
- Sanjeev Arora and Boaz Barak. Computational complexity. A modern approach. Cambridge University Press, Cambridge, 2009.
- Peter Bürgisser and Felipe Cucker. Condition: The geometry of numerical algorithms, volume 349 of Grundlehren der Mathematischen Wissenschaften. Springer, Heidelberg, 2013.
- David Cox, John Little, and Donal O’Shea. Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra. Undergraduate Texts in Mathematics. Springer, New York, third edition, 2007.
- Jean-Pierre Dedieu. Points fixes, zéros et la méthode de Newton, volume 54 of Mathématiques & Applications (Berlin). Springer, Berlin, 2006.
- Swastik Kopparty, Shubhangi Saraf, and Amir Shpilka. Equivalence of polynomial identity testing and polynomial factorization. Comput. Complexity, 24(2):295–331, 2015. Available at https://link.springer.com/article/10.1007/s00037-015-0102-y.
- Gregorio Malajovich. Nonlinear equations. Publicações Matemáticas do IMPA. [IMPA Mathematical Publications]. Instituto Nacional de Matemática Pura e Aplicada (IMPA), Rio de Janeiro, 2011. 28 Colóquio Brasileiro de Matemática. [28th Brazilian Mathematics Colloquium] Available at http://www.labma.ufrj.br/~gregorio/nonlinear/nonlinear.pdf.
- Juan Sabia. Algorithms and their complexities. In Solving polynomial equations, volume 14 of Algorithms Comput. Math., pages 241–268. Springer, Berlin, 2005.
- Andrew J. Sommese, Jan Verschelde, and Charles W. Wampler. Introduction to numerical algebraic geometry. In Solving polynomial equations, volume 14 of Algorithms Comput. Math., pages 301–335. Springer, Berlin, 2005.
- Sascha Timme. Black box factorization of multivariate polynomials. Bachelor Thesis at Technische Universität Berlin. 2015. Available at http://www3.math.tu-berlin.de/algebra/teaching/theses/2015-bsc-sascha-timme.pdf.
Information for students
We encourage every participating student to write lecture notes for their presentation. We hope these notes will accumulate into a coherent whole.
For BMS students receiving a grade from this seminar, it is compulsary to write the lecture notes. Grade assesment for BMS students will be based on a comprehensive evaluation of these notes together with the oral presentation.
Organization and Contact
This seminar is organized by Prof. Dr. Peter Bürgisser in collaboration with Dr. Alperen Ali Ergür and Josué Tonelli Cueto. For any doubt or question, you might contact any of them.