Math 648: Algorithmic Algebraic Geometry (Fall 2011)

Algorithmic Algebraic Geometry (Fall 2011)

Math 648 (Sec. 600)

TuTh: 15:55-17:10, ENPH 201

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. While algebraic geometry pursued deeper and deeper abstract questions in the 20th century, the need for robust and efficient algorithms for equation solving has always remained. Especially now, applications such as chemistry, signal processing, robotics, coding theory, optimization, mathematical biology, computer vision, game theory, and statistics need efficient polynomial system solving.

Math 648 gives an introduction to algebraic geometry from a quantitative and algorithmic point of view. Students completing this course will be well-prepared to understand recent developments in areas such as algebraic complexity, algorithmic number theory, coding theory, and computational algebra. Also, the foundations are presented from a broad point of view, emphasizing the connections of algebraic geometry to number theory and combinatorics.

Policies and Syllabus

Handouts, Homework, and Other Announcements

Office Hours: W 13:00-17:00, and by appointment, in Milner 206

MAIN REFERENCES:

SUPPLEMENTAL REFERENCES:




































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.
  • Note: Since this course presents some very results, this syllabus is subject to change. (Last updated 8/31/2011.)