Solving Polynomial Systems by Polyhedral Homotopies

本课题旨在利用同伦延拓方法对多项式系统进行数值求解。多年来的实践证明，同伦方法是求解多项式系统的有效、可靠和强大的方法。近年来，利用牛顿多面体对多项式系统的稀疏结构进行建模，导致了多面体同伦方法在计算上的重大突破。在此基础上，由PI和他的学生制作的源代码HOM4PS，在效率和存储要求方面远远领先于所有其他现有的求解多项式系统的代码。然而，在实际应用中，有许多大型多项式系统的模型仍然没有一个令人满意的攻击线。而对于大系统来说，跟踪同伦路径的数值技术显然还远远没有完全发展起来。该项目的实质是在对求解器HOM4PS进行深入研究的基础上，对其各方面进行超前开发，从而大大扩大其应用范围，特别是在大型系统中的应用。多项式系统的求解问题经常出现在科学和工程的各个领域，如公式构造、几何相交、逆运动学、机器人、pq指定基的潮流问题、视觉和化学反应方程平衡态的计算等。这一课题在欧洲一直是一个重要的研究课题。在过去十年中，在欧洲委员会的支持下，七个国家和二十所大学在两个连续的重大项目PoSSo和FRISCO中针对这个问题进行了大量的研究工作。如上所述，由pi为这个问题开发的代码HOM4PS要先进得多，当前项目的最终目标是一个更完整的高质量块盒软件，它将结合最先进的技术，为一般科学界提供在各种先进架构上求解多项式系统的可靠来源。

The project is aiming at solving polynomial systems numerically by thehomotopy continuation method. Over the years, practical evidences have beengiven that the homotopy method is efficient, reliable and much powerful insolving polynomial systems. Recently, modeling the sparse structure of apolynomial system by its Newton polytopes leads to a major computationalbreakthrough called the polyhedral homotopy method. Based on it, a sourcecode HOM4PS, produced by the PI and his students, leads all the otherexisting codes for solving polynomial systems in efficiency and storagerequirement by a great margin. Nonetheless, there are numerous models oflarge polynomial systems in application still do not have a satisfactoryline of attack. And it has become apparent that the numerical techniques forfollowing homotopy paths are far from thoroughly developed for largesystems. The essence of the project is the advance development in allaspects of the solver HOM4PS based on the conduct of further research togreatly enlarge the scope of its applications, especially applications tolarge systems.The problem of solving polynomial systems arises very frequently in variousfields of science and engineering, such as formula construction, geometricintersection, inverse kinematics, robotics, power flow problems withPQ-specified bases, vision and the computation of equilibrium states ofchemical reaction equations, etc. This topic has been an important researchsubjectin Europe. In the last decade, a considerable research effortinvolving seven countries and twenty universities had been directed to thisproblem in two consecutive major projects, PoSSo and FRISCO, supported byEuropean Commission. As mentioned above, the code HOM4PS developed by the PIfor this problem is far more advanced and the ultimate goal of the currentproject is a more complete high-quality block-box software which willincorporate the best state of the art to provide the general scientificcommunity a reliable source for solving polynomial systems on a wide varietyof advanced architectures.