On Polyhedral Homotopy and Matroid Intersection

Student Algebraic Geometry Seminar
Friday, February 23, 2018 - 10:00
1 hour (actually 50 minutes)
Skiles 006
Georgia Tech
Polyhedral homotopy methods solve a sparse, square polynomial system by deforming it into a collection of square "binomial start systems." Computing a complete set of start systems is generally a difficult combinatorial problem, despite the successes of several software packages. On the other hand, computing a single start system is a special case of the matroid intersection problem, which may be solved by a simple combinatorial algorithm. I will give an introduction to polyhedral homotopy and the matroid intersection algorithm, with a view towards possible heuristics that may be useful for polynomial system solving in practice.