Message length effects for solving polynomial systems on a hypercube

Polynomial systems of equations frequently arise in solid modelling, robotics, computer vision, chemistry, chemical engineering, and mechanical engineering. Locally convergent iterative methods such as quasi-Newton methods may diverge or fail to find all meaningful solutions of a polynomial system. Recently a homotopy algorithm has been proposed for polynomial systems that is guaranteed globally convergent (always converges from an arbitrary starting point) with probability one, finds all solutions to the polynomial system, and has a large amount of inherent parallelism. For this homotopy algorithm and a given decomposition strategy, the communication overhead for several possible communication stritegies is explored empirically in this paper. The experiments were conducted on an iPSC-32 hypercube.Peer Reviewedhttp://deepblue.lib.umich.edu/bitstream/2027.42/27982/1/0000415.pd