DATE: | Monday, July 30th |
TIME: | 11:00 AM - 12:00 PM |
PLACE: | McConnell 320 |
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.