Solving Eigenvalue Problems of Real Nonsymmetric Matrices with Real Homotopies
T. Y. Li, Zhonggang Zeng, Luan Cong · SIAM Journal on Numerical Analysis · 1992
The eigenvalue problem of a matrix A can be considered a system of polynomial equations $Az - \lambda z = 0$ in complex variables $\lambda \in C$ and $z \in C^n $. In this paper, a homotopy continuation algorithm for solving eigenvalue problems of real nonsymmetric matrices is developed based on this point. Different from current homotopy continuation methods for real nonsymmetric matrices, this algorithm makes use of the homotopy which consists of real polynomials. Hence when a complex path is followed, its conjugate path is obtained as a by-product. Moreover, techniques including a double step inverse iteration are developed to eliminate complex computations completely. A great amount of operations is saved with these complex-to-real conversions. The algorithm employed the strategy of “divide and conquer,” which makes most of the eigen-paths almost straight lines and extremely easy to follow. Although some of the paths may contain bifurcation, the situation is handled with a complexification process which provides a smooth transition from real space to complex space or vice versa. The numerical results for upper Hessenberg matrices of numerous dimensions with randomly generated entries are presented. They clearly demonstrated the $O(n^3 )$ complexity of the authors algorithm for those examples.