Homotopy methods to solve polynomial systems are well suited for parallel computing because the solution paths defined by the homotopy can be tracked independently. For sparse polynomial systems, polyhedral methods give efficient homotopy algorithms. The polyhedral homotopy methods run in three stages: (1) compute the mixed volume; (2) solve a random coefficient start system; (3) track solution paths to solve the target system. This paper is about how to parallelize the second stage in PHCpack. We use a static workload distribution algorithm and achieve a good speedup on the cyclic n-roots benchmark systems. Dynamic workload balancing leads to reduced wall times on large polynomial systems which arise in mechanism design.
2000 Mathematics Subject Classification. Primary 65H10. Secondary 14Q99, 68W30.
Key words and phrases. Continuation methods, load balancing, parallel computation, path following, polynomial systems, polyhedral homotopies.
Proceedings of the 2006 International Conference on Parallel Processing Workshops. 14-18 Augustus 2006. Columbus, Ohio. High Performance Scientific and Engineering Computing. Edited by Timothy Mark Pinkston and Fusun Ozguner. Pages 481-488, IEEE Computer Society, 2006.