| Home | Research Topic | People | Colloquia | Research Projects | Pictures |
MSRI-UP 2017 will focus on algorithms for the efficient solution of systems of polynomial equations. Students will learn about recent approaches via tropical geometry and A-discriminants, along with important connections to algorithmic complexity. This summer's research program will be led by Prof. J. Maurice Rojas of Texas A&M University. Students with a strong linear algebra background will profit most from this research opportunity.
Solutions of systems of polynomial equations are central in numerous current applications within engineering, biochemistry, and dynamical systems. Approximating these solutions lies at the intersection of numerical analysis and algebraic geometry, and the study of polynomial equations goes all the way back to the ancient Greeks. However, the theoretical foundations for efficient polynomial system solving algorithms were only understood toward the late 20th century. This is in part because complexity theory (and cheap computing power) did not arrive until the 20th century. Also, it wasn't until the 1970s that many beautiful connections between algebraic geometry and combinatorics were discovered. These connections were the basis of what we now call toric and tropical geometry.
For example, in 1974, Bernstein discovered that the number of complex roots of certain polynomial systems could be expressed as a mixed volume of polytopes. This formula led to numerous algorithmic speed-ups, and complexity lower bounds, within algorithmic algebraic geometry. Later, around 1994, Gelfand, Kapranov, and Zelevinsky found that the image of any complex polynomial zero set under the coordinate-wise log absolute value map has a polyhedral structure. The latter result, along with earlier work of Hadamard, Viro, and others, led to tropical geometry --- the study of piece-wise linear manifolds as a means of understanding polynomial zero sets. More recently, work of Cheng, Denef, Gao, Khovanski, Rojas, and Wan shows that tropical methods can be used to understand polynomial zero sets over rings other than the complex numbers.
One consequence of this development is that one no longer needs to make a long detour into commutative algebra in order to begin learning algebraic geometry: If one approaches the subject from the point of view of sparse polynomials, then the basic results (on binomial equations) are easily derivable via calculus and linear algebra. To move on to more general polynomial systems, one is then naturally led to consider the A-discriminant --- a far-reaching generalization of the classical quadratic discriminant. Until recently, one could only learn of A-discriminants in certain graduate courses. However, recent work of Dickenstein, Rojas, Sturmfels, and others has shown that one can use tropical geometry to approach the subject much more quickly and easily. This is the approach used for the 2-week lecture series that introduces the students to algorithmic algebraic geometry. The projects then focus on implementing algorithms for working with A-discriminants, visualizing tropical varieties over the real numbers, and quantitative aspects of sparse polynomials.