Math 648: Algorithmic Algebraic Geometry (Fall 2009)

Algorithmic Algebraic Geometry (Fall 2009)

Math 648 (section 600)

TuTh: 11:10-12:25, Room: Milner 313

Instructor: Prof. J. Maurice Rojas
E-mail: rojas@math.tamu.edu
Web Page: http://www.math.tamu.edu/~rojas

Algebraic geometry was born over two millenia ago, with the aim of understanding how to solve polynomial equations. Ironically, algebraic geometry courses nowadays rarely talk about the most efficient way to solve a system of equations one may encounter in practice. The need for robust and efficient algorithms for algebraic geometry is now motivated by numerous applications: even a short list would have to include chemistry, signal processing, robotics, coding theory, optimization, mathematical biology, computer vision, game theory, and statistics.

Math 648 gives an introduction to algebraic geometry from an algorithmic point of view. Students completing this course will be well-prepared to understand recent developments in areas such as algebraic complexity, algebraic statistics, algorithmic number theory, coding theory, and computational algebra. This course also provides valuable background for, and an alternative perspective to, more abstractly oriented courses on algebraic geometry.

Logistics and Policies

Handouts, Homework, and Other Announcements

Office Hours: Milner 206, by appointment
Syllabus:
We'll cover topics in numerical analysis (NA) not usually covered in any algebraic geometry class, topics in algebraic geometry (AG) not usually covered in any numerical analysis class, and topics in algorithmic complexity not usually covered in any course on NA or AG. The precise topics will most likely be a subset of the following:
  • Applications of polynomial system solving and external motivations for algebraic and arithmetic geometry...
  • Preliminaries on binomial systems
  • Random polynomials and the harmonious fundamental theorem of algebra
  • Amoeba theory in low-dimensions
  • Homotopy inspired proof of the Fundamental Theorem of Algebra
  • Smale's 17th Problem
  • Topological and geometric preliminaries
  • Algebraic preliminaries, including univariate discriminants
  • Descartes' Rule of Signs and an easy proof of a weak version which extends to exponential sums
  • The univariate case of the Gelfond-Kazarnovski-Khovanski theorem on complex fewnomials
  • Many polyhedral connections along the way...
  • Newton's method
  • Smale's alpha theory and the effective inverse function theorem
  • The robust alpha theorem and an intro to univariate polynomial equation sol ving
  • Projective space
  • Bezout's Theorem with multiplicities
  • Kushnirenko's Theorem and an outline of its proof
  • Toric Varieties
  • Stochastic Kushnirenko's Theorem via the momentum map
  • Some facts on algebraic curves and completing Kushnirenko's Theorem
  • The A-Discriminant
  • Bernstein's Theorem and an outline of its proof
  • Mixed Subdivisions
  • Toric Resultants
  • ...and Turing/BSS Complexity, P=?NP, Numerical conditioning, Homotopy Algorithms, Khovanski's Theorem on Fewnomials, Effective Nullstellensatze, Resultants and Eigensolving, Semi-Algebraic Sets, Connections to Number Theory, Connections to Semidefinite Programming.

    • Look daunting? Don't panic: We develop everything from the ground up, with just a little linear algebra!

    MAIN REFERENCES:

  • [BCSS98] Complexity and Real Computation, by L. Blum, F. Cucker, M. Shub, and S. Smale, Springer-Verlag 1998.
  • [Roj09] Algorithmic Complexity in Algebraic Geometry, by J. Maurice Rojas, in preparation.
  • [Stu02] Solving Systems of Polynomial Equations, by Bernd Sturmfels, CBMS Lecture Series, AMS Press, 2002.
  • Course Reader (a constantly growing collection of excerpts from recent books, expository papers, and research papers).

    SUPPLEMENTAL REFERENCES:

  • [Ahl78] Complex Analysis, Lars V. Ahlfors, 3rd ed., International Series in Pure and Applied Mathematics, McGraw-Hill Book Co., 1978.
  • [BS96] Algorithmic Number Theory, Eric Bach and Jeff Shallit, MIT Press, 1996.
  • [CLO97] Ideals, Varieties, and Algorithms, by David A. Cox, John B. Little, and Donal O'Shea, Springer-Verlag, 1997.
  • [CLO98] Using Algebraic Geometry, by David A. Cox, John B. Little, and Donal O'Shea, Springer-Verlag, 1998.
  • [Ewa96] Combinatorial Convexity and Algebraic Geometry, by Gunter Ewald, Springer-Verlag, 1996.
  • [GKZ94] Discriminants, Resultants, and Multidimensional Determinants, by Israel M. Gel'fand, Misha M. Kapranov, and Andrei V. Zelevinsky, Mathematics: Theory & Applications, Birkhauser Boston, Inc., Boston, MA, 1994.
  • [IMS09] Tropical Algebraic Geometry, by Ilia Itenberg, Grigory Mikhalkin, and Evgenii Shustin; Oberwolfach Seminars, Birkhauser Basel, 2nd ed., 2009.
  • [Pap94] Computational Complexity, by Christos H. Papadimitriou, Addison-Wesley, Reading, MA, 1994.
  • [Sch86] Theory of Linear and Integer Programming, by Alexander Schrijver, Wiley-Interscience Series in Discrete Mathematics, 1986.
  • [Zie95] Lectures on Polytopes, Gunter M. Ziegler, Springer-Verlag, 1995.