Solving Polynomial Systems by Polyhedral Homotopies

通过多面体同伦求解多项式系统

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

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.

该项目的目标是用同伦连续方法数值求解多项式方程组。多年来，同伦方法在求解多项式方程组中是一种高效、可靠和强大的方法。近年来，利用牛顿多面体来模拟非多项式系统的稀疏结构，导致了一个重大的计算突破，称为多面体同伦方法。在此基础上，由PI及其学生编写的源代码HOM4PS在效率和存储要求上大大优于现有的多项式方程组求解程序。尽管如此，仍有大量的大型多项式系统模型在应用中仍然不具备攻击的安全性.很明显，对于大型系统，跟踪同伦路径的数值技术还远远没有得到充分的发展。本课题的实质是在深入研究的基础上，对HOM4PS进行全方位的改进，以扩大其应用范围，特别是大系统的应用范围，多项式方程组的求解问题在科学和工程的各个领域中经常出现，如公式构造、几何求交、逆运动学、机器人学、PQ基潮流问题、视觉和化学反应方程式平衡态的计算等，这一课题在欧洲已成为一个重要的研究课题。在过去的十年中，在欧盟委员会支持的两个连续的重大项目PoSSo和FRISCO中，涉及七个国家和二十所大学的相当大的研究努力针对这个问题。如上所述，PI为这个问题开发的代码HOM4PS要先进得多，当前项目的最终目标是一个更完整的高质量块盒软件，它将结合最先进的技术，为一般科学界提供一个可靠的来源，用于在各种先进的架构上解决多项式系统。