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.