Complexity of Path-Following Methods for the Eigenvalue Problem

Abstract

A unitarily invariant projective framework is introduced to analyze the complexity of path-following methods for the eigenvalue problem. A condition number, and its relation to the distance to ill-posedness, is given. A Newton map appropriate for this context is defined, and a version of Smale's $\gamma$-Theorem is proven. The main result of this paper bounds the complexity of path-following methods in terms of the length of the path in the condition metric.

43 pages

References in corpus (3)

• Some Open Problems in Random Matrix Theory and the Theory of Integrable Systems. II
• Adaptative Step Size Selection for Homotopy Methods to Solve Polynomial Equations
• Smale's Fundamental Theorem of Algebra reconsidered