**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:
- Root Counting Methods
- Numerical Irreducible Decomposition
- 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.