Maria Sosonkina
Abstract
Homotopy algorithms to solve a nonlinear system of equations f(x) = 0 involve tracking the zero curve of a homotopy map p(a, λ, x) from λ = 0 until λ = 1. When the algorithm nears or crosses the hyperplane λ = 1, an “end game” phase is begun to compute the solution x¯ satisfying p(a, λ, x¯) = f(x¯) = 0. This note compares several end game strategies, including the one implemented in the normal flow code FIXPNF in the homotopy software package HOMPACK.
- MORGAN, A. P. AND WATSON, L.T. 1989. A globally convergent parallel algorithm for zeros of polynomial systems. Nonlinear Anal. 13, 1339-1350. Google Scholar
- WATSON, L. T. 1989. Globally convergent homotopy methods: A tutorial. Appl. Math. Comput. 31BK, 369-396.Google Scholar
- WATSON, L. T., BILLUPS, S. C., AND MORGAN, A.P. 1987. HOMPACK: A suite of codes for globally convergent homotopy algorithms. ACM Trans. Math. Softw. 13, 3 (Sept.), 281-310. Google Scholar
Index Terms
- Note on the end game in homotopy zero curve tracking
Recommendations
Algorithm 652: HOMPACK: a suite of codes for globally convergent homotopy algorithms
There are algorithms for finding zeros or fixed points of nonlinear systems of equations that are globally convergent for almost all starting points, i.e., with probability one. The essence of all such algorithms is the construction of an appropriate ...
Algorithm 801: POLSYS_PLP: a partitioned linear product homotopy code for solving polynomial systems of equations
Globally convergent, probability-one homotopy methods have proven to be very effective for finding all the isolated solutions to polynomial systems of equations. After many years of development, homotopy path trackers based on probability-one homotopy ...
Algorithm 857: POLSYS_GLP—a parallel general linear product homotopy code for solving polynomial systems of equations
Globally convergent, probability-one homotopy methods have proven to be very effective for finding all the isolated solutions to polynomial systems of equations. After many years of development, homotopy path trackers based on probability-one homotopy ...
Reviews
Donald G. M. Anderson
In essence, the homotopy method for solving a system of nonlinear equations f x =0 consists of choosing a function h x,t such that h x,1 =f x and h x 0 ,0 =0 for known x 0 , then tracing the path x t defined by h x t ,t =0 and x 0 =x 0 to a solution x &d4; =x 1 of the original system. Assuming that such a path exists, it suffices to follow it closely enough to arrive in a neighborhood of x &d4; ,1 such that an end game iteration will converge rapidly to the solution. Difficulties arise if the Jacobian of h is rank deficient at one or more points on the path, especially at x &d4; ,1 . Watson participated in the development of a well-known code package, HOMPACK, implementing a number of path-following techniques. The current work examined several candidate end game iterations through experiments on a published suite of challenging test problems. When all were successful, these candidates were comparable, so their performance was ranked based on cases in which one but not all of them failed to converge. A preferred candidate emerged and is recommended as a replacement for that used in HOMPACK. The comparison appears to be indicative but not definitive.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments