"Matrix Methods for Sparse Polynomial Systems" John Canny jfc@cs.berkeley.edu Prof. John Canny Computer Science Division 529 Soda Hall Berkeley CA 94720-1776 jfc@cs.berkeley.edu There are a variety of ways of solving polynomial systems in many variables. The systems that arise in engineering problems often have few solutions relative to their Bezout bound, which is the product of their degrees. A sharper measure is the Bernstein bound which is based on the Newton polytopes of the system. I will give a short introduction to Newton polytopes and the mixed volumes, and explain how the latter bounds the number of roots. The mixed volume can be defined using a mixed subdivision of a polytope. This subdivision has been used by B. Sturmfels to derive an efficient equation-solving method based on homotopies, and by us to derive efficient resultant matrices. In both cases, the complexity depends on the sparse bound rather than Bezout. Given a sparse resultant matrix, any polynomial equation solving problem reduces to an eigenvalue calculation.