A Robust Numerical Path Tracking Algorithm for Polynomial Homotopy Continuation

Simon Telen, Marc Van Barel, and Jan Verschelde

Abstract:

We propose a new algorithm for numerical path tracking in polynomial homotopy continuation. The algorithm is 'robust' in the sense that it is designed to prevent path jumping and in many cases, it can be used in (only) double precision arithmetic. It is based on an adaptive stepsize predictor that uses Padé techniques to detect local difficulties for function approximation and danger for path jumping. We show the potential of the new path tracking algorithm through several numerical examples and compare with existing implementations.