A homotopy for solving general polynomial systems that respects m-homogeneous structures

摘要

Methods for finding all solutions to a polynomial system, F(z) = 0, of n equations in n unknowns using a generic homotopy have been presented by several researchers over the last ten years. In this paper we describe a new method for defining a homotophy to find all solutions to a polynomial system. A major feature of this new approach is that the homotopy need not to be “generic” or “random.” The practical consequences are that the homotopy may be chosen to more closely resemble the system being solved, with a consequent potential for reducing the arc length of paths and exploiting special structures in the original system. In particular, if the system is naturally m-homogeneous, then the number of homotopy paths that need to be tracked is reduced. Since many systems that arise in applications have such a structure, this represents a significant advance over previous homotopies. We also provide a proof that the homotopy parameter is strictly increasing on homotopy paths as a function of arc length, a new result which has implications for the choice of numerical path-tracking algorithms.