A robust path tracking algorithm for homotopy continuation

Conventional path tracking algorithms used in homotopy continuation systems sometimes miss roots owing to jumping from one segment of the homotopy path to another even if there exists homotopy paths to the roots. A robust path tracking algorithm is proposed which loses significant efficiency only on those portions of the path where segment jumping is likely to occur. The method presented here basically performs the predictor-corrector procedure using the Euler predictor and the Newton corrector. Any available algorithm can be used to control the step size. Robustness is achieved by adding the following rule: control the step size so that each continuation step causes a reasonably small change in the determinant of the augmented Jacobian. Case studies have shown that allowing -50 to +100% change virtually eliminates segment jumping in all the path-tracking algorithms tested. The determinant monitoring step size control algorithm can be applied to most of the currently available path tracking algorithms so that extremely tangled homotopy paths can be traced, finding all roots on them.