Mathematical Sciences: Homotopy Algorithms for Solving Sparse Polynomial Systems

日期：1995年5月19日星期五10：19：42 -0400（美国东部时间）发件人：Tien-Yien Li li@math.msu.edu收件人：thaler@nsf.gov主题：回复：提案DMS-9504953 Mime-版本：1.0尊敬的Thaler博士： 感谢您关于我的提案DMS-9504953的部分资金的消息。 求解稀疏多项式方程组的同伦算法 最近，它已被证明，建模的稀疏结构的多项式系统的牛顿多面体导致一个重大的计算突破，解决多项式系统的同伦方法。该项目中提出的PIıs“随机乘积同伦”方法旨在为随机乘积形式的同伦构造一个起始系统，其牛顿多面体包含目标系统的牛顿多面体。另一方面，“多面体同伦”的基础上一个优雅的公式计算混合体积可以找到所有零的多项式系统以下少得多，在大多数情况下的确切数量，同伦曲线。 多项式系统在数学、科学和技术中无处不在。非常小的系统很容易用手解决，但较大的系统无法可靠地解决，如果有的话。该项目的目的是实现一个便携式求解器使用最新的多项式系统求解算法，并能够被纳入应用程序。将进行研究，以推进最先进的技术和我们对多项式系统的理解;此外，还将研究各种应用领域，如运动学，控制理论，几何建模和生物化学，其中出现的问题可简化为多项式系统解决。

Date: Fri, 19 May 1995 10:19:42 -0400 (EDT) From: Tien-Yien Li li@math.msu.edu To: thaler@nsf.gov Subject: Re: Proposal DMS-9504953 Mime-Version: 1.0 Dear Dr. Thaler: Thank you for your message concerning the partial funding of my proposal DMS-9504953. Homotopy algorithms for solving sparse polynomial systems Recently, it has been proved that modeling the sparse structure of a polynomial system by its Newton polytopes leads to a major computational breakthrough in solving polynomial systems by homotopy methods. The PIıs "random product homotopy" approach proposed in the project intends to construct a start system for the homotopy in random product form with its Newton polytopes containing those of the target system. On the other hand, the "polyhedral homotopy" based on an elegant formula for computing the mixed volume can find all zeros of a polynomial system by following much fewer, in most occasions the exact amount of, homotopy curves. Polynomial Systems occur everywhere in Mathematics, Science and Technology. Very small systems are easily solved by hand, but larger systems cannot reliably be so solved, if at all. The project aims to implement a portable solver using the latest in polynomial system solving algorithms and capable of being incorporated into applications programs. Research will be carried out to advance the state of the art and our understanding of polynomial systems; additionally, various application areas will be studied, such as kinematics, control theory, geometric modelling, and biochemistry in which problems reducible to polynomial system solving arise.