loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
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
Jan Verschelde, University of Illionois at Chicago, USA
Yan Zhuang, University of Illinois at Chicago, USA
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
Usage of this product signifies your acceptance of the Terms of Use.