|DATE:||Monday, July 30th|
|TIME:||11:00 AM - 12:00 PM|
|TITLE:||Geometric Methods for Solving Algebraic Systems|
|SPEAKER:||Ioannis Z. Emiris, INRIA Sophia-Antipolis, France|
A major algebraic approach for solving systems of polynomial equations is based on the resultant (or eliminant) of such a system. The relatively recent theory of sparse elimination exploits the structure of the equations in order to obtain tighter bounds on the number of roots and better complexity in numerically approximating them. The model of sparsity is of combinatorial geometric nature, thus leading to certain questions in general-dimensional convex geometry.
This talk overviews the sparse resultant method and discusses two geometric problems related to constructing a matrix expressing this resultant. Both problems deal with Minkowski sums of convex polytopes in a dimension given by the dimension of the polynomial system (typically between 3 and 20). The first is the computation of a subset of the integer points inside a Minkowski sum, and the second is the construction of a mixed subdivision of such a sum. Public domain implementations and some applications are described.