McGill University - School of Computer Science

Algorithms Seminar Summer 2001

Everybody is welcome!

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.

Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at Algorithms Seminar organization.