权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Polyhedral Homotopy Continuation Methods for Computing All Real and Complex Solutions of Systems of Polynomial Equations

计算多项式方程组全实数和复数解的多面体同伦延拓方法

基本信息

批准号：
13650444
负责人：
KOJIMA Masakazu
金额：
$ 1.92万
依托单位：
Tokyo Institute of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2001
资助国家：
日本
起止时间：
2001 至 2002
项目状态：
已结题

项目摘要

The purpose of this research project is to develop practical numerical methods for all real and complex solutions of large scale systems of polynomial equations. The polyhedral homotopy continuation method used in this research consists of the following three phases :Phase 1 : Construction of polyhedral homotopy systems.Phase 2 : Numerical tracing of homotopy paths by the predictor-corrector method.Phase 3 : Verification of solutions.In 2001, we designed and developed basic algorithms for each phase above. In 2002, we studied the following issues.1. Improvement of computational efficiency in each phase. In phase 1, we proposed an efficient construction of homotopy systems arising from symmetric systems of polynomial equations. We incorporated a linear algebra library LAPACK into phase 2, and developed a new method for verifying and classifying solutions of the cyclic polynomial.2. Improvement of numerical stability in each phase. Linear systems to be solved in phase 2 become often so ill-conditioned that computation of their accurate solutions are difficult. We devised new dynamic scaling techniques to resolve this difficulty. We confirmed through numerical experiments that the use of these scaling techniques together with the singular value decomposition worked very effectively to improve the numerical stability of phase 2.3. We combined the three phases into a software package PHoM, and released it through Internet. This software solved some large scale systems of polynomial equations that had not been solved before. In conclusion, this research project has accomplished its purpose mentioned above.4. We have started a parallel implementation of PHoM, which will continue in the next year.

本研究计画的目的是发展实用的数值方法来求解大型多项式方程组的所有真实的和复杂的解。本研究所采用的多面体同伦延拓方法包括以下三个阶段：第一阶段：构造多面体同伦系统;第二阶段：用预测-校正方法数值追踪同伦路径;第三阶段：验证解。2002年，我们研究了以下问题。提高每个阶段的计算效率。在第一阶段，我们提出了一个有效的构造同伦系统所产生的对称系统的多项式方程。我们将线性代数库LAPACK纳入第二阶段，并开发了一种新的方法来验证和分类循环多项式的解决方案。提高各阶段的数值稳定性。在第二阶段中求解的线性方程组往往变得病态，以至于难以计算其精确解。我们设计了新的动态缩放技术来解决这个困难。我们通过数值实验证实，使用这些缩放技术与奇异值分解非常有效地提高了阶段2.3的数值稳定性。我们将这三个阶段组合成一个软件包PHoM，并通过互联网发布。该软件解决了一些以前没有解决过的大型多项式方程组。综上所述，本研究项目达到了上述目的.我们已开始并行实施PHoM，并将在明年继续实施。