Optimization Online


Numerical Stability of Path Tracing in Polyhedral Homotopy Continuation Methods

S. Kim (skim***at***ewha.ac.kr)
M. Kojima (kojima***at***is.titech.ac.jp)

Abstract: The reliability of polyhedral homotopy continuation methods for solving a polynomial system becomes increasingly important as the dimension of the polynomial system increases. High powers of the homotopy continuation parameter $t$ and ill-conditioned Jacobian matrices encountered in tracing of homotopy paths affect the numerical stability. We present modified homotopy functions with a new homotopy continuation parameter $s$ and various scaling strategies to enhance the numerical stability. Advantages of employing the new homotopy parameter $s$ are discussed. Numerical results are included to illustrate improved performance of the presented techniques.

Keywords: Polynomial system, Polyhedral homotopy continuation methods, Path tracing, Numerical stability.

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

Citation: Research report B-380, Department of Mathematical and Computing Sciences, Tokyo Institute of Technoloy 2-12-1 Oh-Okayama, Meguro-ku, Tokyo 152-8552 Japan March/2003

Download: [Postscript][Compressed Postscript][PDF]

Entry Submitted: 03/26/2003
Entry Accepted: 03/26/2003
Entry Last Modified: 03/26/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