Mathematical Sciences: Homotopy Algorithms for Solving Sparse Polynomial Systems

数学科学：求解稀疏多项式系统的同伦算法

基本信息

批准号：
9504953
负责人：
Tien-Yien Li
金额：
$ 6.7万
依托单位：
Michigan State University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
1995
资助国家：
美国
起止时间：
1995-07-15 至 1998-06-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=9504953&HistoricalAwards=false
关键词：
Mathematical Sciences Homotopy Algorithms Solving

项目摘要

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.

日期： 1995 年 5 月 19 日星期五 10:19:42 -0400 (EDT) 发件人：Tien-Yien Li li@math.msu.edu 至：thaler@nsf.gov 主题：回复：提案 DMS-9504953 Mime 版本：1.0亲爱的 Thaler 博士：感谢您就我的提案 DMS-9504953 的部分资金提供的信息。用于求解稀疏多项式系统的同伦算法最近，已经证明通过牛顿多胞形对多项式系统的稀疏结构进行建模导致了通过同伦方法求解多项式系统的重大计算突破。该项目打算构建一个随机乘积形式的同伦起始系统，其牛顿多面体包含目标系统的“多面体”。 “同伦”基于计算混合体积的优雅公式，可以通过遵循更少（在大多数情况下是精确数量）的同伦曲线来找到多项式系统的所有零点。多项式系统在数学、科学和技术中随处可见。非常小的系统很容易通过手工求解，但较大的系统无法可靠地求解（如果有的话）。该项目旨在使用最新的多项式系统求解算法来实现便携式求解器，并且能够将其纳入应用程序中。推进最先进的技术和我们对多项式系统的理解；此外，还将研究各种应用领域，例如运动学、控制理论、几何建模和生物化学，其中出现的问题可简化为多项式系统求解。