2006 International Conference on Parallel Processing Workshops (ICPPW'06)
Parallel Implementation of the Polyhedral Homotopy Method
Columbus, Ohio
August 14-August 18
ISBN: 0-7695-2637-3
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.
Index Terms:
Continuation methods, load balancing, parallel computation, path following, polynomial systems, polyhedral homotopies.
Citation:
Jan Verschelde, Yan Zhuang, "Parallel Implementation of the Polyhedral Homotopy Method," icppw, pp.481-488, 2006 International Conference on Parallel Processing Workshops (ICPPW'06), 2006