Solving polynomial systems by polyhedral homotopies

在过去的二十年里，求解多项式系统的同伦连续法已经建立，并被证明是可靠和有效的。根据之前的一个项目，在NSF Grant DMS-9804846的支持下，产生了源代码HOM4PS。这种编码在大量多项式系统上的优异性能为新开发的方法构成了一个强大的通用求解器提供了实际证据。然而，仍然有许多多项式系统的模型在应用中没有令人满意的攻击路线。这些模型为有趣和具有挑战性的问题提供了丰富的来源，具有很强的数学内容。本课题的实质是在进一步研究的基础上对求解器进行超前开发，大大扩大了求解器的应用范围。最终的目标是一个更完整的高质量的块盒软件，它将结合最先进的技术，为一般科学界提供一个可靠的资源，在实践中求解多项式系统。求解多项式系统的问题一直是，并将继续是最重要的学科之一，在理论和应用数学。在科学和工程的各个领域，如公式构造、几何求交、逆运动学、机器人、视觉和化学反应方程的平衡态计算等，经常需要求解多项式方程组。近年来(1993-1999)，欧洲连续两个重大项目POSSO(多项式系统求解)和FRISCO(集成符号/数值计算框架)对这一问题进行了大量的研究，欧洲7个国家的13个大学团队参与了这一研究。这些研究项目的重点是在计算机代数的框架内发展已经很成熟的Groebner基方法。它们对符号处理的依赖使得这些方法看起来似乎局限于相对较小的问题。相比之下，同伦延拓方法在本项目中的逼近是数值的，并显示出强大的应用结果。

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.