Globally convergent homotopy methods: A tutorial (Q582009)

The paper begins by introducing globally convergent homotopy methods with an example inverse problem related to cantilever beams. The next section deals with theory, and concentrate on conditions for which, in various practical settings, the homotopy path will lead from the initial guess to the solution. Theorems related to Brouwer fixed points, general zero- finding, optimization, and two-point boundary value problems discretized with shooting, finite differences, collocation, and finite elements are given. The third section deals with path-following algorithms for problems with dense Jacobian matrices; it treats ODE-based algorithms, normal flow algorithms, and augmented Jacobian matrix algorithms. Substantial detail is given, but not so much that clarity is sacrificed. The fourth section provides an overview of the software package HOMPACK. This package contains instantiations of the three path-following algorithms for three path-following algorithms for three problem types and for both dense and sparse Jacobian matrices. Lists of the HOMPACK routines grouped by function occur. Section 5 contains pointers to references in which applications are discussed. Section 6 discusses parallel implementation of the methods on hypercubes Experimental results for polynomial systems, in which each path is assigned to a node, are given for the Intel iPSC-32 and a test set from General Motors. There are 83 references.