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

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

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.