Solving polynomial systems

Many problems in kinematics and robotics lead naturally to systems of polynomial equations. Numerous algorithms have been developed for finding the solutions of a polynomial system over centuries. Examples are Newton-Raphson’s iteration method, interval analysis, optimization based method and genetic algorithm (GA) etc. However my research focuses on methods that can obtain all solutions to a polynomial system, particularly the polynomial homotopy continuation method and resultant elimination method.

  • Homotopy continuation method

    Homotopy method, also called “continuation method,” for polynomial systems were first proposed by Garcia and Zangwill (1977). The idea is based on the fact that small changes on the coefficients of the polynomial systems will result small changes to the roots. Starting at roots of a “start system”, homotopy method traces the solution along the so-called “homotopy/solution paths” as the start system is continuously transformed into the target system.

    is a high performance homotopy solver written in Fortran 90. It accepts Generalized Linear Product (GLP) start system to reduce number of divergent solution path. It has been parallelized using Message Passing Interface (MPI) so that it can run on the parallel distributed memory multiprocessors, such as UCI’s Beowulf system, the Blue Horizon and Data Star system at the San Diego Supercomputer Center. See link to the software page for details.

  • Resultant elimination methods

    While polynomial homotopy method provides a solution to median and large polynomial systems, it is computationally demanding. In the situation when computation time is essential, resultant elimination is preferable. The main advantages of resultant method lies in the fact that the resultant can always be expressed in terms of matrices and determinants. As a result, we are able to use algorithms from linear algebra and obtain tight bounds on the running time. Furthermore, resultant formulation can be pre-processed offline. For this reason, resultant methods provide the most efficient solution for small and median polynomial systems. However finding valid resultant elimination steps can be challenging.

Homepage