Homotopy Methods for Solving Polynomial Systems
tutorial at ISSAC 2005, July 24-27, 2005.
Key Laboratory of Mathematics Mechanization, Beijing, China

Download the notes for the tutorial (pdf format).

Go to the PHCpack download page to download executable versions of phc.
Download a collection of examples used in the tutorial.

Slides for the three lectures:

Motivation

Homotopy continuation methods [Li, 2003] provide symbolic-numeric algorithms to solve polynomial systems. We apply Newton's method to follow solution paths defined by a family of systems, a so-called homotopy. The homotopy connects the system we want to solve with a system which is easier to solve. While the path following algorithms are essential numerical algorithms, the creation of the homotopy can be regarded as a symbolic operation. The performance of the homotopy continuation solver is primarily determined by the selection of a homotopy which matches best the structure of the given polynomial system.

Outline

As the tutorial will be two hours and 30 minutes, divided in three lectures, each spanning about 40 minutes:
  1. Root Counting Methods
  2. Numerical Irreducible Decomposition
  3. Software and Applications

Prerequisites

A basic introductory course in numerical analysis should do. We assume familiarity with concepts as numerical stability and conditioning, see chapters 3 and 4 of [Stetter, 2004]. Newton's method in several variables is our point of departure.

References

Leykin and Verschelde, 2004
Anton Leykin and Jan Verschelde:
PHCmaple: A Maple Interface to the Numerical Homotopy Algorithms in PHCpack. The Abstract, manuscript in gzipped ps, and in pdf format.
In Proceedings of the Tenth International Conference on Applications of Computer Algebra (ACA'2004), edited by Quoc-Nam Tran, pages 139-147, 2004.

Li, 2003
T.Y. Li.
Numerical solution of polynomial systems by homotopy continuation methods.
In F. Cucker, editor, Handbook of Numerical Analysis. Volume XI. Special Volume: Foundations of Computational Mathematics, pages 209--304. North-Holland, 2003.

Sommese and Wampler, 2005
Andrew J. Sommese and Charles W. Wampler:
The Numerical solution of systems of polynomials arising in engineering and science.
World Scientific Press, Singapore, 2005.

Sommese, Verschelde, and Wampler, 2003
Andrew J. Sommese, Jan Verschelde, and Charles W. Wampler:
Numerical Irreducible Decomposition using PHCpack. The Abstract and gzipped postscript file, manuscript in pdf format.
In Algebra, Geometry and Software Systems, edited by M. Joswig and N. Takayama, pages 109-130, Springer-Verlag 2003.

Sommese, Verschelde, and Wampler, 2005
Andrew J. Sommese, Jan Verschelde, and Charles W. Wampler:
Introduction to Numerical Algebraic Geometry. The Abstract and gzipped postscript file, manuscript in pdf format.
In A. Dickenstein and I.Z. Emiris (Eds.), Solving Polynomial Equations: Foundations, Algorithms, and Applications. Volume 14 of Algorithms and Computation in Mathematics 14, pages 339-392, Springer-Verlag, 2005.

Stetter, 2004
Hans J. Stetter:
Numerical Polynomial Algebra.
SIAM, 2004.

Sturmfels, 2002
Bernd Sturmfels:
Solving Systems of Polynomial Equations.
Number 97 of CBMS Regional Conference Series in Mathematics, AMS 2002.

Verschelde, 1999a
Jan Verschelde:
Algorithm 795: PHCpack: A general-purpose solver for polynomial systems by homotopy continuation.
ACM Transactions on Mathematical Software 25(2): 251-276, 1999. Abstract and (gzipped .ps file) ; see also html version of the paper.

Verschelde, 1999b
Jan Verschelde:
Polynomial Homotopies for Dense, Sparse and Determinantal Systems.
MSRI Preprint #1999-041 The Abstract and (gzipped .ps file). Also, a hypertext version is available.