Solving Polynomial Systems by Polyhedral Homotopies

该项目的目标是用同伦延拓方法数值求解多项式系统。多年来的实践证明，同伦方法是一种高效、可靠、功能强大的求解多项式系统的方法。最近，用牛顿多面体来模拟非多项式系统的稀疏结构，导致了一项重大的计算突破，称为多面体同伦方法。在此基础上，由PI和他的学生们开发的源码HOM4PS在效率和存储要求上远远领先于现有的求解多项式系统的代码。尽管如此，仍然有许多大多项式系统的模型在应用中仍然没有一个令人满意的攻击线。很明显，跟踪同伦路径的数值技术对于大型系统来说还远远没有得到彻底的发展。该项目的实质是在进一步研究的基础上，对求解器HOM4PS的各个方面进行了进一步的发展，以极大地扩大其应用范围，特别是在大型系统中的应用。多项式系统的求解问题经常出现在科学和工程的各个领域，如公式构造、几何求交、逆运动学、机器人学、具有PQ指定基的潮流问题、视觉和化学反应方程的平衡态计算等。这一课题一直是欧洲的一个重要研究课题。在过去的十年里，在欧盟委员会的支持下，连续两个重大项目--POSSO和FRISCO--对这个问题进行了相当大的研究，涉及7个国家和20所大学。如上所述，由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.