Parallel Homotopy Algorithms to Solve Polynomial Systems
Parallel Homotopy Algorithms to Solve Polynomial Systems
复制标题
求解多项式系统的并行同伦算法
DOI：
10.1007/11832225_22
复制
发表时间：
2006
影响因子：
1.4
通讯作者：
Zhuang Yan
中科院分区：
文献类型：
--
作者：
A. Leykin;J. Verschelde;Zhuang Yan
用于计算多项式系统所有孤立解的数值逼近的同伦连续方法被称为“令人尴尬的并行”，即：由于其低通信开销，这些方法在大量处理器上具有很好的伸缩性。由于许多重要的问题仍然没有解决，主要是由于它们固有的计算复杂性，所以不开发多项式同伦连续方法的并行实现将是尴尬的。本文是关于“并行PHCpack”的开发，这个项目是几年前与王玉松合作开始的，目前还在继续Anton Leykin(并行不可约分解)和严庄(并行多面体同伦)。我们报告了我们为使PHCPack准备好解决应用中出现的大型多项式系统所做的努力。
2000年数学学科分类。主65H10。中学14Q99，68W30。
Homotopy continuation methods to compute numerical approximations to all isolated solutions of a polynomial system are known as “embarrassingly parallel”, i.e.: because of their low communication overhead, these methods scale very well for a large number of processors. Because so many important problems remain unsolved mainly due to their intrinsic computational complexity, it would be embarrassing not to develop parallel implementations of polynomial homotopy continuation methods. This paper concerns the development of “parallel PHCpack”, a project which started a couple of years ago in collaboration with Yusong Wang, and which currently continues with Anton Leykin (parallel irreducible decomposition) and Yan Zhuang (parallel polyhedral homotopies). We report on our efforts to make PHCpack ready to solve large polynomial systems which arise in applications.
2000 Mathematics Subject Classification. Primary 65H10. Secondary 14Q99, 68W30.