Analysis of Function Component Complexity for Hypercube Homotopy Algorithms

Probability-one homotopy algorithms are a class of methods for solving nonlinear systems of equations that are globally convergent from an arbitrary starting point with probability one. The essence of these homotopy algorithms is the construction of a homotopy map ra and the subsequent tracking of a smooth curve g in the zero set ra-1 (0) of ra . Tracking the zero curve g requires repeated evaluation of the map ra its n x (n + 1) Jacobian matrix Dra , and numerical linear algebra for calculating the kernel of Dra . This paper analyzes parallel homotopy algorithms on a hypercube, briefly reviewing the numerical linear algebra, several communication topologies and problem decomposition strategies, and concentrating on function component complexity, problem size, and the effect of different component complexity distributions. These parameters interact in complicated ways, but some general principles can be inferred based on empirical results. Implications for developing reliable and efficient parallel mathematical software packages for this problem area are also discussed.