CAMPUS THEORY SEMINAR
Part of the SCIENCE AT THE EDGE Seminar Series
Friday, March 23, 2001
11:30am, Room 224 Physics-Astronomy Building
Refreshments served at 11:15am
SOLVING POLYNOMIAL SYSTEMS
T. Y. Li
Department of Mathematics
Michigan State University
Numerically solving isolated zeros of polynomial systems in affine space
has become increasingly important in applications. Many engineering
models, such as formular construction, geometric interection problems,
inverse kinematics, power flow problem with PQ-specified bases, the most
general six degree of freedom manipulators, computation of equilibrium
states, etc.
Elimination theory based methods, most notably the Buchberger algorithm
for constructing Groebner bases, are the classical approach to solving
systems of polynomial equations, but its reliance on symbolic manipulation
makes it seem unsuitable for all but small problems. Moreover, the method
reduces the problem to the ill-conditioned problem of numerically solving a
high-degree polynomial equation in one variable.
In this talk, a new approach, developed in the last two decades, by using
the homotopy continuation method will be surveyed. The method involves
first solving a trivial system, and then deforming these solutions along
smooth paths to the solutions of the target system. The method has been
successfully implemented in solving many polynomial systems, and the
amount of computation required to find all solutions can be made roughly
proportional to the number of solutions.