Optimization Online


PHoM - a Polyhedral Homotopy Continuation Method for Polynomial Systems

Takayuki Gunji (gunji1***at***is.titech.ac.jp)
Sunyoung Kim (skim***at***ewha.ac.kr)
Masakazu Kojima (kojima***at***is.titech.ac.jp)
Akiko Takeda (akiko.takeda***at***toshiba.co.jp)
Katsuki Fujisawa (fujisawa***at***r.dendai.ac.jp)
Tomohiko Mizutani (mizutan8***at***is.titech.ac.jp)

Abstract: PHoM is a software package in C++ for finding all isolated solutions of polynomial systems using a polyhedral homotopy continuation method. Among three modules constituting the package, the first module StartSystem constructs a family of polyhedral-linear homotopy functions, based on the polyhedral homotopy theory, from input data for a given system of polynomial equations $\f(\x) = \0$. The second module CMPSc traces the solution curves of the homotopy equations to compute all isolated solutions of $\f(\x) = \0$. The third module Verify checks whether all isolated solutions of $\f(\x)=\0$ have been approximated correctly. We describe numerical methods used in each module and the usage of the package. Numerical results to demonstrate the performance of PHoM include some large polynomial systems that have not been solved previously.

Keywords: Polynomials, Homotopy continuation methods, Polyhedral homotopy, Numerical experiments, Software package

Category 1: Nonlinear Optimization (Nonlinear Systems and Least-Squares )

Citation: Research report number B-386, Tokyo Institute of Technology, Dec./2002

Download: [Postscript][PDF]

Entry Submitted: 01/15/2003
Entry Accepted: 01/15/2003
Entry Last Modified: 01/15/2003

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society