Communications in Information and Systems

Volume 12 (2012)

Number 3

Spherical projective path tracking for homotopy continuation methods

Pages: 195 – 220

DOI: http://dx.doi.org/10.4310/CIS.2012.v12.n3.a2

Authors

Tianran Chen (Department of Mathematics, Michigan State University, East Lansing, Mich., U.S.A.)

Tien-Yien Li (Department of Mathematics, Michigan State University, East Lansing, Mich., U.S.A.)

Abstract

Solving systems of polynomial equations is an important problem in mathematics with a wide range of applications in many fields. The homotopy continuation method is a large class of reliable and efficient numerical methods for solving systems of polynomial equations. An essential component in the homotopy continuation method is the path tracking algorithm for tracking smooth paths of one real dimension. In this regard, “divergent paths” pose a tough challenge as the tracking of such paths is generally impossible. The existence of such paths is, in part, caused by $\mathbb{C}^n$, the space in which homotopy methods usually operate, being non-compact. A well known remedy is to operate inside the complex projective space $\mathbb{CP}^n$ instead. Path tracking inside $\mathbb{CP}^n$ is the focus of this article. Taking the Riemannian geometry of $\mathbb{CP}^n$ into account, we derive the basic algorithm for projective path tracking using the sphere, $S^{2n + 1}$, as the model of computation. Remarkable results from numerical experiments using this method are presented.

Full Text (PDF format)