Parallel implementation of the polyhedral homotopy method
Parallel implementation of the polyhedral homotopy method
复制标题
多面体同伦法的并行实现
DOI：
10.1109/icppw.2006.61
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Yan Zhuang
中科院分区：
文献类型：
--
作者：
J. Verschelde;Yan Zhuang
求解多项式系统的同伦方法非常适合并行计算，因为可以独立跟踪同伦定义的解路径。对于稀疏多项式系统，多面体方法给出了有效的同伦算法。多面体同伦方法分三个阶段运行：（1）计算混合体积； (2)求解随机系数启动系统； (3)跟踪求解目标系统的求解路径。本文是关于如何并行化 PHCpack 中的第二阶段。我们使用静态工作负载分配算法，并在循环 n 根基准测试系统上实现了良好的加速。动态工作负载平衡可减少机制设计中出现的大型多项式系统的挂壁时间
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