Volume 73, Number 4, 329-348, DOI: 10.1007/s00607-004-0070-6

Numerical Stability of Path Tracing in Polyhedral Homotopy Continuation Methods

S. Kim and M. Kojima

View Related Documents

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 the improved performance of the presented techniques.

AMS Subject Classifications:  65H10 - 65H20

Keywords  Polynomial system - polyhedral homotopy continuation methods - path tracing - numerical stability

A considerable part of this work was conducted while this author was visiting Tokyo Institute of Technology. Research supported by Kosef R004-000-2001-00200.

Fulltext Preview

Image of the first page of the fulltext document