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 Grant DMS-9804846 的支持下，产生了源代码 HOM4PS。该代码在各种应用中的大量多项式系统上的出色性能提供了实际证据，表明新开发的方法构成了强大的通用求解器。尽管如此，在应用中仍然有许多多项式系统模型没有令人满意的攻击线。这些模型提供了丰富的有趣且具有挑战性的问题，并且具有很强的数学内容。本项目的实质是在进一步研究的基础上对求解器进行超前开发，大大扩大其应用范围。最终目标是一个更完整的高质量块盒软件，它将结合最先进的技术，为一般科学界提供在实践中解决多项式系统的可靠来源。解决多项式系统的问题已经并将继续是，纯粹数学和应用数学中最重要的学科之一。 在科学和工程的各个领域，如公式构造、几何交、逆运动学、机器人、视觉和化学反应方程平衡态的计算等，求解多项式方程组的需求非常频繁。近年来(1993 -1999年），欧洲在两个连续的重大项目PoSSo（多项式系统求解）和FRISCO（Framwork for综合符号/数值计算），由欧盟委员会支持，涉及七个欧洲国家的十三所大学团队。这些研究项目的重点是在计算机代数框架内开发已经完善的 Groebner 基本方法。 它们对符号操作的依赖使得这些方法似乎有些局限于相对较小的问题。相比之下，本项目中的同伦延拓方法是数值方法，并表现出更强大的应用结果。