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

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

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.