Solving polynomial systems by polyhedral homotopies

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

• 批准号: 0104009
• 负责人: Tien-Yien Li
• 金额: $ 16.72万
• 依托单位: Michigan State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-08-01 至 2005-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0104009&HistoricalAwards=false
• 关键词: Solving; polynomial; systems; polyhedral; homotopies

In the last two decades, the homotopy continuation method forsolving polynomial systems has been established and proved tobe reliable and efficient. Resulting from a previous project,supported by NSF Grant DMS-9804846, a source code, HOM4PS, wasproduced. Excellent performance of this code on a large collectionof polynomial systems in a wide variety of applications providespractical evidence that the newly developed methods constitute apowerful general purpose solver. Nontheless, there are stillnumerous models of polynomial systems in applications which donot have a satisfactory line of attack. Those models provide a richsource of interesting and challenging problems with strong mathematicalcontent. The essence of the proposed project is the advance developmentof the solver based on the conduct of further researchto greatly enlarge the scope of its applications. The ultimate goalis a more complete high-quality block-box solfware which willincorporate the best state of the art to provide the general scientificcommunity a reliable source for solving polynomial systems in practice.The problem of solving polynomial systems has been, and will continueto be, one of the most important subjects in both pure and appliedmathematics. The need to solve systems of polynomial equations arisesvery 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 chemicalreaction equations, etc. In recent years (1993-1999), a considerableresearch effort in Europe had been directed to this problem in twoconsecutive major projects, PoSSo (Polynomial System Solving) and FRISCO(FRamework for Integrated Symbolic/numerical COmputation), supported byEuropean Commission with thirteen university teams in seven Europeancountries involved. Those research projects focused on the developmentof the already well-established Groebner basis methods within theframework of computer algebra. Their reliance on symbolic manipulationmakes those methods seem somewhat limited to relatively small problems.In contrast, the approch by the homotopy continuation method in thisproject is numerical and exhibits much powerful application results.

在过去的二十年里，同伦连续方法被建立起来，并被证明是可靠和有效的。由于以前的一个项目，由NSF资助DMS-9804846，源代码，HOM 4PS，wasproduced。该代码在各种应用中的大量多项式系统上的出色性能提供了实际证据，表明新开发的方法构成了一个强大的通用求解器。尽管如此，在实际应用中仍然有大量的多项式系统模型没有一个令人满意的攻击线。这些模型提供了丰富的有趣和具有挑战性的问题，具有很强的理论内容。该项目的实质是在对求解器进行进一步研究的基础上，对求解器进行超前开发，以大大扩大其应用范围.最终的目标是一个更完整的高质量的块盒软件，它将结合最好的艺术状态，为广大科学界提供一个可靠的来源，在实践中解决多项式系统的问题已经是，并将继续是，在纯数学和应用数学中最重要的课题之一。 多项式方程组的求解在科学和工程的各个领域中都是非常频繁的，如公式构造、几何求交、逆运动学、机器人学、视觉以及化学反应方程组平衡态的计算等（1993-1999年），欧洲在两个连续的重大项目中针对这一问题进行了大量研究，PoSSo（Polynomial System Solving）和FRISCO（Framework for Integrated Symbolic/Numerical Compulation），由欧盟委员会支持，涉及七个欧洲国家的十三个大学团队。这些研究项目的重点是在计算机代数的框架内发展已经成熟的Groebner基础方法。 这些方法对符号操作的依赖使它们似乎只限于相对较小的问题，而同伦延拓方法则是数值方法，并显示出很强的应用效果。