Homotopy-determinant algorithm for solving nonsymmetric eigenvalue problems
HTML articles powered by AMS MathViewer
- by T. Y. Li and Zhong Gang Zeng PDF
- Math. Comp. 59 (1992), 483-502 Request permission
Abstract:
The eigenvalues of a matrix A are the zeros of its characteristic polynomial \[ f(\lambda ) = \det [A - \lambda I].\] With Hyman’s method of determinant evaluation, a new homotopy continuation method, homotopy-determinant method, is developed in this paper for finding all eigenvalues of a real upper Hessenberg matrix. In contrast to other homotopy continuation methods, the homotopy-determinant method calculates eigenvalues without computing their corresponding eigenvectors. Like all homotopy methods, our method solves the eigenvalue problem by following eigen-value paths of a real homotopy whose regularity is established to the extent necessary. The inevitable bifurcation and possible path jumping are handled by effective processes. The numerical results of our algorithm, and a comparison with its counterpart, subroutine HQR in EISPACK, are presented for upper Hessenberg matrices of numerous dimensions, with randomly generated entries. Although the main advantage of our method lies in its natural parallelism, the numerical results show our algorithm to be strongly competitive also in serial mode.References
- Shui Nee Chow, John Mallet-Paret, and James A. Yorke, Finding zeroes of maps: homotopy methods that are constructive with probability one, Math. Comp. 32 (1978), no. 143, 887–899. MR 492046, DOI 10.1090/S0025-5718-1978-0492046-9
- Moody T. Chu, A note on the homotopy method for linear algebraic eigenvalue problems, Linear Algebra Appl. 105 (1988), 225–236. MR 945638, DOI 10.1016/0024-3795(88)90015-8
- Moody T. Chu, T.-Y. Li, and Tim Sauer, Homotopy method for general $\lambda$-matrix problems, SIAM J. Matrix Anal. Appl. 9 (1988), no. 4, 528–536. MR 964666, DOI 10.1137/0609043
- J. J. M. Cuppen, A divide and conquer method for the symmetric tridiagonal eigenproblem, Numer. Math. 36 (1980/81), no. 2, 177–195. MR 611491, DOI 10.1007/BF01396757 J. J. Dongarra and M. Sidani, A parallel algorithm for the non-symmetric eigenvalue problem, Technical Report, Comp. Sci. Dept. CS-91-137, Univ. of Tennessee.
- J. J. Dongarra and D. C. Sorensen, A fully parallel algorithm for the symmetric eigenvalue problem, SIAM J. Sci. Statist. Comput. 8 (1987), no. 2, S139–S154. Parallel processing for scientific computing (Norfolk, Va., 1985). MR 879400, DOI 10.1137/0908018 M. Hyman, Eigenvalues and eigenvectors of general matrices, presented at the 12th National Meeting of the Association for Computing Machinery, Houston, Texas, June 1957.
- Ilse C. F. Ipsen and Elizabeth R. Jessup, Solving the symmetric tridiagonal eigenvalue problem on the hypercube, SIAM J. Sci. Statist. Comput. 11 (1990), no. 2, 203–229. MR 1037511, DOI 10.1137/0911013 E. Jessup, Parallel solution of the symmetric eigenvalue problem, Ph.D. Thesis, Yale University, 1989.
- T. Y. Li and N. H. Rhee, Homotopy algorithm for symmetric eigenvalue problems, Numer. Math. 55 (1989), no. 3, 265–280. MR 993472, DOI 10.1007/BF01390054
- T.-Y. Li and T. Sauer, Homotopy method for generalized eigenvalue problems $Ax=\lambda Bx$, Linear Algebra Appl. 91 (1987), 65–74. MR 888479, DOI 10.1016/0024-3795(87)90060-7
- Tien-Yien Li, Tim Sauer, and James A. Yorke, Numerical solution of a class of deficient polynomial systems, SIAM J. Numer. Anal. 24 (1987), no. 2, 435–451. MR 881375, DOI 10.1137/0724032
- T. Y. Li, Zhong Gang Zeng, and Luan Cong, Solving eigenvalue problems of real nonsymmetric matrices with real homotopies, SIAM J. Numer. Anal. 29 (1992), no. 1, 229–248. MR 1149095, DOI 10.1137/0729015
- Tien-Yien Li, Hong Zhang, and Xian-He Sun, Parallel homotopy algorithm for the symmetric tridiagonal eigenvalue problem, SIAM J. Sci. Statist. Comput. 12 (1991), no. 3, 469–487. MR 1093202, DOI 10.1137/0912026
- Sy-Shin Lo, Bernard Philippe, and Ahmed Sameh, A multiprocessor algorithm for the symmetric tridiagonal eigenvalue problem, SIAM J. Sci. Statist. Comput. 8 (1987), no. 2, S155–S165. Parallel processing for scientific computing (Norfolk, Va., 1985). MR 879401, DOI 10.1137/0908019 B. T. Smith et al., Matrix eigensystem routines—EISPACK guide, 2nd ed., Springer-Verlag, 1976. B. L. Van der Waerden, Modern algebra. Vol. 1, Ungar, New York, 1949.
- J. H. Wilkinson, Error analysis of floating-point computation, Numer. Math. 2 (1960), 319–340. MR 116477, DOI 10.1007/BF01386233
Additional Information
- © Copyright 1992 American Mathematical Society
- Journal: Math. Comp. 59 (1992), 483-502
- MSC: Primary 65F15; Secondary 65F40, 65H17, 65H20
- DOI: https://doi.org/10.1090/S0025-5718-1992-1151113-4
- MathSciNet review: 1151113