Solving Polynomial Systems by the Polyhedral Homotopy

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

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.