Solving Polynomial Systems by the Polyhedral Homotopy

用多面体同伦求解多项式系统

• 批准号: 1115587
• 负责人: Tien-Yien Li
• 金额: $ 24万
• 依托单位: Michigan State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-09-15 至 2015-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1115587&HistoricalAwards=false
• 关键词: Solving; Polynomial; Systems; Polyhedral; Homotopy

A group led by the PI has successfully developed a software package, HOM4PS-2.0, implementing the "polyhedral homotopy continuation" method for solving polynomial systems. The solver leads existing software packages for solving polynomial systems in speed by a large margin. The essence of the proposed project is the further development in all aspects of the solver HOM4PS-2.0. In particular, for the need of solving larger polynomial systems, a major aspect of the project is the advanced development of the parallel version of the solver. The landscape of computation hardware is quite different from even a decade ago. Developments in new processor design and network technology have allowed supercomputers and computer clusters to grow larger and faster than ever, including new ideas such as cycle scavenging, grid computing, virtual supercomputers, multiple cores, and GPUs (graphics processing units). The proposed project will investigate and implement versions of HOM4PS-2.0 that take optimum advantage of heterogeneous computing platforms, with special emphasis on clusters, cloud computing, multicore and GPUs. In addition we plan to find ways to implement highly serial parts of the original algorithm, such as mixed volume computation and path-jumping detection on parallel architectures. The proposed project intends to fully incorporate all the cutting-edge parallel computing technologies in our solver for solving larger and larger polynomial systems. The problem of solving polynomial systems arises very frequently in various fields of science and engineering, such as, formula construction, geometric intersection, inverse kinematics, robotics, computer vision and the computation of equilibrium states of chemical reaction equations, etc. Science and engineering problems pose an increasing demand for solving larger and larger polynomial systems. To deal with such large systems, more computing resources are needed to greatly enlarge the capability of our solver, HOM4PS-2.0. For this purpose the parallelization of the original algorithms becomes inevitably essential. Computational technology is experiencing a major sea change in which one either rides the wave or goes under. To embrace this challenge, the core of the project is to fully incorporate the cutting-edge parallel computing technologies for solving larger and larger polynomial systems. The ultimate goal is a more powerful suite of high-quality software package which will provide the scientific community a reliable source for solving polynomial systems in practice.

PI领导的小组成功开发了软件包HOM4PS-2.0，实现了求解多项式系统的“多面体同伦延拓”方法。该求解器在速度上远远领先于现有的多项式系统求解软件包。拟议项目的本质是求解器 HOM4PS-2.0 各个方面的进一步开发。特别是，针对求解更大多项式系统的需求，该项目的一个主要方面是并行版本求解器的高级开发。计算硬件的面貌与十年前已有很大不同。新处理器设计和网络技术的发展使得超级计算机和计算机集群比以往任何时候都变得更大、更快，其中包括循环清理、网格计算、虚拟超级计算机、多核和 GPU（图形处理单元）等新想法。拟议项目将研究和实施 HOM4PS-2.0 版本，充分利用异构计算平台，特别强调集群、云计算、多核和 GPU。此外，我们计划找到方法来实现原始算法的高度串行部分，例如并行架构上的混合体积计算和路径跳跃检测。拟议的项目旨在将所有尖端的并行计算技术完全融入我们的求解器中，以求解越来越大的多项式系统。多项式系统的求解问题在科学和工程的各个领域中经常出现，例如公式构造、几何交、逆运动学、机器人、计算机视觉和化学反应方程平衡态的计算等。 科学和工程问题对求解越来越大的多项式系统提出了越来越大的需求。为了处理如此大型的系统，需要更多的计算资源来极大地扩大我们的求解器 HOM4PS-2.0 的能力。为此，原始算法的并行化不可避免地变得至关重要。计算技术正在经历一场巨大的变革，要么乘风破浪，要么沉沦。为了迎接这一挑战，该项目的核心是充分结合尖端的并行计算技术来解决越来越大的多项式系统。最终目标是一套更强大的高质量软件包，它将为科学界提供在实践中解决多项式系统的可靠来源。