Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Homotopy-determinant algorithm for solving nonsymmetric eigenvalue problems

Authors: T. Y. Li and Zhong Gang Zeng
Journal: Math. Comp. 59 (1992), 483-502
MSC: Primary 65F15; Secondary 65F40, 65H17, 65H20
MathSciNet review: 1151113
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The eigenvalues of a matrix A are the zeros of its characteristic polynomial

$\displaystyle 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 [Enhancements On Off] (What's this?)

  • [1] S-N. Chow, J. Mallet-Paret, and J. A. Yorke, Finding zeros of maps: homotopy methods that are constructive with probability one, Math. Comp. 32 (1978), 887-899. MR 492046 (80d:55002)
  • [2] M. T. Chu, A note on the homotopy method for linear algebraic eigenvalue problems, Linear Algebra Appl. 105 (1988), 225-236. MR 945638 (89g:65039)
  • [3] M. T. Chu, T. Y. Li, and T. Sauer, Homotopy method for general $ \lambda $-matrix problems, SIAM J. Matrix Anal. Appl. 9 (1988), 528-536. MR 964666 (89m:65052)
  • [4] J. J. J. M. Cuppen, A divide and conquer method for the symmetric tridiagonal eigenproblem, Numer. Math. 36 (1981), 177-195. MR 611491 (82d:65038)
  • [5] 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.
  • [6] J. J. Dongarra and D. C. Sorensen, A fully parallel algorithm for the symmetric eigenvalue problem, SIAM J. Sci. Statist. Comput. 8 (1987), 139-154. MR 879400 (88f:65054)
  • [7] M. Hyman, Eigenvalues and eigenvectors of general matrices, presented at the 12th National Meeting of the Association for Computing Machinery, Houston, Texas, June 1957.
  • [8] I. Ilse and E. Jessup, Solving the symmetric tridiagonal eigenvalue problem on the hypercube, SIAM J. Sci. Statist. Comput. 11 (1990), 203-229. MR 1037511 (90m:65076)
  • [9] E. Jessup, Parallel solution of the symmetric eigenvalue problem, Ph.D. Thesis, Yale University, 1989.
  • [10] T. Y. Li and N. H. Rhee, Homotopy algorithm for symmetric eigenvalue problems, Numer. Math. 55 (1989), 265-280. MR 993472 (90g:65074)
  • [11] T. Y. Li and T. Sauer, Homotopy method for generalized eigenvalue problems $ A{\mathbf{x}} = \lambda B{\mathbf{x}}$, Linear Algebra Appl. 91 (1987), 65-74. MR 888479 (88f:65058)
  • [12] T. Y. Li, T. Sauer, and J. Yorke, Numerical solution of a class of deficient polynomial systems, SIAM J. Numer. Anal. 24 (1987), 435-451. MR 881375 (89e:90181)
  • [13] T. Y. Li, Z. Zeng, and L. Cong, Solving eigenvalue problems of real nonsymmetric matrices with real homotopies, SIAM J. Numer. Anal. 29 (1992), 229-248. MR 1149095 (92i:65075)
  • [14] T. Y. Li, H. Zhang, and X. H. Sun, Parallel homotopy algorithm for symmetric tridiagonal eigenvalue problems, SIAM J. Sci. Statist. Comput. 12 (1991), 464-485. MR 1093202 (91k:65070)
  • [15] S.S. Lo, B. Philippe, and A. Sameh, A multiprocessor algorithm for the symmetric tridiagonal eigenvalue problem, SIAM J. Sci. Statist. Comput. 8 (1987), 155-165. MR 879401
  • [16] B. T. Smith et al., Matrix eigensystem routines--EISPACK guide, 2nd ed., Springer-Verlag, 1976.
  • [17] B. L. Van der Waerden, Modern algebra. Vol. 1, Ungar, New York, 1949.
  • [18] J. H. Wilkinson, Error analysis of floating-point computation, Numer. Math. 2 (1960), 319-340. MR 0116477 (22:7264)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65F15, 65F40, 65H17, 65H20

Retrieve articles in all journals with MSC: 65F15, 65F40, 65H17, 65H20

Additional Information

Article copyright: © Copyright 1992 American Mathematical Society

American Mathematical Society