Solving Polynomial Systems by the Polyhedral Homotopy

多项式系统经常出现在科学和工程的各个领域，如公式构造、几何相交、逆运动学、机器人、视觉和化学反应方程平衡状态的计算。因此，对这类系统的数值求解算法的需求很大。多年来的实践证明，同伦延拓方法在数值求解多项式系统方面是有效、可靠和强大的。最近，一项被称为多面体同伦方法的重大计算突破出现了，使该方法大大提高了效率和功能。基于这种新方法，PI开发的软件包HOM4PS-2.0在求解大量多项式系统方面取得了令人惊叹的性能，并且在效率和存储需求方面大大领先于其他所有现有代码。本课题的实质是在进一步开展研究的基础上，对求解器HOM4PS-2.0及其并行化版本HOM4PS-2.0para进行各方面的进一步开发，大大扩大了应用范围，特别是对超大系统的应用。该项目的最终目标是更完整的高质量黑盒软件，它将为一般科学界提供在各种先进架构上求解多项式系统的可靠来源。

Polynomial systems arise very frequently in various fields of science and engineering, such as formula construction, geometric intersection, inverse kinematics, robotics, vision, and the computation of equilibrium states of chemical reaction equations. Algorithms for solving such systems numerically are therefore highly in demand.Over the years, practical evidence has been given that homotopy continuation methods are efficient, reliable, and powerful in solving polynomial systems numerically. Recently, a major computational breakthrough called the polyhedral homotopy method emerged, making the method considerably more efficient and powerful. Based on this new method, the software package HOM4PS-2.0 developed by the PI has produced marvelous performance on solving a large collection of polynomial systems and has led all the other existing codes in efficiency and storage requirement by a huge margin.The essence of the proposed project is the further development in all aspects of the solver HOM4PS-2.0 as well as its parallelized version HOM4PS-2.0para, based on the conduction of further research to greatly enlarge the scope of the applications, especially applications to very large systems. The ultimate goal of the project is more-complete high-quality black-box software which will provide the general scientific community a reliable source for solving polynomial systems on a wide variety of advanced architectures.