Mathematical Sciences: Homotopy Algorithms for Solving Sparse Polynomial Systems

点击翻译按钮获取中文摘要

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.