Algorithm 710: FORTRAN subroutines for computing the eigenvalues and eigenvectors of a general matrix by reduction to general tridiagonal form

ABSTRACT

This paper describes programs to reduce a nonsymmetric matrix to tridiagonal form, to compute the eigenvalues of the tridiagonal matrix, to improve the accuracy of an eigenvalue, and to compute the corresponding eigenvector. The intended purpose of the software is to find a few eigenpairs of a dense nonsymmetric matrix faster and more accurately than previous methods. The performance and accuracy of the new routines are compared to two EISPACK paths: RG and HQR-INVIT. The results show that the new routines are more accurate and also faster if less than 20 percent of the eigenpairs are needed.

REFERENCES

• 1: DONGARRA, J. J. Improving the accuracy of computed matrix eigenvalues. Tech. Rep. ANL-80-84, Argonne National Laboratory, Chicago, Ill., Aug. 1980.
• 2: DONGARRA, J. J., MOLER, C. B., AND WILKINSON, J.H. Improving the accuracy of computed elgenvalues and eigenvectors. SIAM J Numer. Anal. 20, i (Feb. 1983), 23-45.
• 3: FRANCIS, J. G.F. The QR transformation Part 2. Comput. J. 4, 4 (Oct. 1961), 332-345.
• 4: GEIST, G.A. Reduction of a general matrix to tndiagonal form. Tech. Rep. ORNL/TM-10991, Oak Ridge National Laboratory, Oak Ridge, Tenn., Feb. 1989
• 5: George A. Geist, Reduction of a general matrix to tridiagonal form, SIAM Journal on Matrix Analysis and Applications, v.12 n.2, p.362-373, April 1991 [doi>10.1137/0612026]
• 6: GELS?, G A., Lu, A, AND W^CHSPRES$, E, L. Stabilized Gaussian reduction of an arbitrary matrix to tridiagonal form. Tech. Rep. ORNL/TM-11089, Oak Ridge National Laboratory, Oak Ridge, Tenn., Feb. 1989.
• 7: GOLUB, G. H., AND VAN LOAN, C.F. Matrtx Cornputatzons. Johns Hopkins University Press, Baltimore, Md., 1983.
• 8: R^LL, L. B. Comptltational Solution of Nonlinear Operator Equations. Wiley, New York, 1969.
• 9: RUTISHAUSER, H. Solution of e~genvalue problems with the LR transformation. Nat. Bur. Standards Appl. Math. Ser. 49 (1958), 47-81.
• 10: SMrrH, B. T., BOYLE, J. M., DONGARRA, J. J., GARABOW, B. S., IKEBE, Y., KLEMA, V. C., AND MOLER, C. B. Matrix Elgensystern Routtnes--EISPACK Guzde. Springer-Verlag, Heidelberg, 1974
• 11: J. H. Wilkinson, The algebraic eigenvalue problem, Oxford University Press, Inc., New York, NY, 1988

INDEX TERMS

Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Eigenvalues and eigenvectors (direct and iterative methods)
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms

Keywords:
condensed form, eigenvalues, nonsymmetric, numerical algorithms