Mathematical Sciences: Homotopy Continuation Method for Deficient Polynomial Systems

数学科学：缺陷多项式系统的同伦延拓法

• 批准号: 8902663
• 负责人: Tien-Yien Li
• 金额: $ 5.74万
• 依托单位: Michigan State University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1989
• 资助国家: 美国
• 起止时间: 1989-07-01 至 1991-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8902663&HistoricalAwards=false
• 关键词: Mathematical; Sciences; Homotopy; Continuation; Method

8902663 Li Most systems of n polynomial equations in n unknowns arising in applications are "deficient", in the same sense that they have fewer solutions than that predicted by the total degree of the system. A procedure is introduced and will be examined in light of efficiency and applicability for finding all the isolated zeros of deficient polynomial systems which need to be solved repetitively with varying coefficients. The procedure is based on the cheater's homotopy, a continuation method which follows paths to all solutions. All solutions are found with an amount of computational work roughly proportional to the actual number of solutions, while previous general methods normally require an amount of computation roughly proportional to the total degree. The research will further investigate the structure of the deficiency on a case-by-case basis. The main concern is, in a specific case, to find an initial polynomial system for the homotopy that is simple to solve and also produces few extraneous homotopy paths.

[8902663]应用中出现的n个未知数的n个多项式方程的大多数系统是“缺陷”的，在同样的意义上，它们的解比系统的总度所预测的解少。本文介绍了一种方法，并将从效率和适用性的角度对需要用变系数重复求解的亏多项式系统的所有孤立零进行检验。该过程基于作弊者的同伦，这是一种跟踪所有解的路径的延拓方法。所有解的计算量与实际解的数量大致成正比，而以前的一般方法通常需要的计算量与总度数大致成正比。这项研究将在个案基础上进一步调查缺陷的结构。主要的问题是，在一个特定的情况下，为同伦找到一个初始的多项式系统，它很容易求解，并且产生很少的多余的同伦路径。