Polyhedral end games for polynomial continuation (Q1272646)

Homotopy continuation methods have been extensively applied for over 20 years to numerically compute all of the solutions of polynomial systems in \(\mathbb{C}^n\). One key problem with this method is that often many homotopy paths lead to solutions at infinity. In such a case, the issue arises of deciding whether a path is diverging or merely converging to a solution with large components. Moreover, solutions at infinity are often also singular, which makes it difficult to determine whether a solution corresponding to a path really lies at infinity. The polyhedral homotopy method based upon Bernshtein's mixed volume bound generically has an exact number of paths for the finite solutions. However, many practical problems are not generic and as a result, homotopy methods based upon the mixed volume bound may still require the tracing of some divergent paths. The present paper deals with determining whether a path is diverging. Algorithms have been given by the authors and their co-authors for producing a start system \(G\) with a complete set of solutions \({\mathbf z}_i \in \mathbb{C}^n-{\mathbf 0}\), so that the homotopy equation \[ H({\mathbf x},t):=(1-t)G({\mathbf x})+tF({\mathbf x})={\mathbf 0} \] gives nonsingular curves \({\mathbf x}_i(t)\) such that \({\mathbf x}_i(0)={\mathbf z}_i\), and all solutions of \(F({\mathbf x})={\mathbf 0}\) are among the limit points \(\lim_{t\to 1}{\mathbf x}_i(t)\). The deficient case occurs when \(F({\mathbf x})={\mathbf 0}\) fails to have the full number of solutions as \(G({\mathbf x})={\mathbf 0}\) has. The technique for determining whether a path is diverging is based upon a proof of Bernshtein's discriminant condition: solution paths which leave \(\mathbb{C}^n-{\mathbf 0}\) correspond to solutions in some face system. A technique is given for numerically estimating an outer normal to the face which causes the deficiency. Identifying the deficient face can lead to the development of better performing homotopies. A further contribution of the paper is an extrapolation method for estimating the cycle number of a path. This number plays an important role in the end game strategies used in several homotopy algorithms.