Solving polynomial systems by 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.