Mathematical Sciences: Homotopy Algorithms for Solving Sparse Polynomial Systems

日期：1995年5月19日星期五10:19:42 -0400（美国东部时间）发件人：李天恩li@math.msu.edu至：thaler@nsf.gov主题：回复：提案DMS-9504953 Mime-Version: 1.0亲爱的塞勒博士：感谢您关于我的提案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.