Robust continuation methods for tracing solution curves of parameterized systems (Q457042)

Let \[ F(x,t)=0,\,\, x\in \mathbb {R}^n,\,\, t \in \mathbb {R}, \] be a parameterized system of nonlinear equations. Assume \(F: \mathbb{R}^{n+1} \rightarrow \mathbb{R}^n\) is smooth, there is a point \(u_0 \in \mathbb{R}^{n+1}\) such that \(F(u_0) = 0\), and the Jacobian matrix \(F'(u_0)\) has maximum rank. Then the solution set of \(F\) contains a smooth curve \(c(s)\), \(s\) the arclength, with \(c(0) = u_0\), and there exists an open interval \(I\) such that for all \(\alpha \in I\), \(c'(\alpha) \neq 0\), and \(\mathrm{rank}(F'(c(\alpha))) = n\). Homotopy continuation, or curve tracing, consists of the iteration of two steps: predicting and correcting. In this paper, the predictor strategy known as the Euler predictor is used, and various corrector strategies are studied. Two corrector strategies often employed are: 1) the plane corrector, which finds the point \(u_{k+1}\) at the intersection of the curve with the hyperplane perpendicular to the tangent of the curve at the point \(u_{k}\) and containing the predicted point \(v_{k+1}\) and 2) the nearest point corrector, which finds the point \(u_{k+1}\) on the curve nearest to the predicted point \(v_{k+1}\). While these methods work well in general if the solution curves are close to each other, or the curve turns sharply at some point, ``curve jumping'' can occur. This forces the predictor steplength to be very small, reducing the overall efficiency of the algorithm. The authors present a new ``sphere corrector'' strategy. The method finds the point \(u_{k+1}\) which is the intersection of the curve, and the sphere whose diameter is the straight line segment joining the points \(u_{k}\) and the predicted point \(v_{k+1}\). This intersection is found using Netwon's method, or variants thereof, and the steplength must be adjusted to make the sphere intersect \(c(s)\) at only the two points \(u_{k}\) and \(u_{k+1}\). The authors prove that the method approximates a solution curve if the steplength is small enough. Further, the steplength is adapted (increased or decreased as necessary) throughout the algorithm using the convergence (or lack thereof) of the iterative method used to find the intersection. The authors suggest using Newton's method, Newton's method with ``line search'' step control or Netwon's method with ``trust region'' step control to solve the nonlinear system generated by the corrector step. The paper concludes with a comparison of the three corrector methods on systems of two concentric circles with various radii. The results illustrate that the sphere corrector method is more robust and efficient than the other two.