Numerical Linear Algebra Aspects of Globally Convergent Homotopy Methods

Abstract

Probability one homotopy algorithms are a class of methods for solving nonlinear systems of equations that are globally convergent with probability one. These methods are theoretically powerful, and if constructed and implemented properly, are robust, numerically stable, accurate, and practical. The concomitant numerical linear algebra problems deal with rectangular matrices, and good algorithms require a delicate balance (not always achieved) of accuracy, robustness, and efficiency in both space and time. The author's experience with globally convergent homotopy algorithms is surveyed here, and some of the linear algebra difficulties for dense and sparse problems are discussed.