Numerical Stability of Path Tracing in Polyhedral Homotopy Continuation Methods

S. Kim (skimewha.ac.kr)
M. Kojima (kojimais.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