QR-like algorithms for the nonsymmetric eigenvalue problem

ABSTRACT

Hybrid codes that combine elements of the QR and LR algorithms are described. The codes can calculate the eigenvalues and, optionally, eigenvectors of real, nonsymmetric matrices. Extensive tests are presented as evidence that, for certain choices of parameters, the hybrid codes possess the same high reliability as the QR algorithm and are significantly faster. The greatest success has been achieved with the codes that calculate eigenvalues only. These can do the task in 15% to 50% less time than the QR algorithm.

REFERENCES

• 1: E. Anderson , Z. Bai , C. Bischof , J. Demmel , J. Dongarra , J. Du Croz , A. Greenbaum , S. Hammarling , A. McKenney , S. Ostrouchov , D. Sorensen, LAPACK's user's guide, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 2: Zhaojun Bai , James Demmel, On a block implementation of Hessenberg multishift QR iteration, International Journal of High Speed Computing, v.1 n.1, p.97-112, May 1989 [doi>10.1142/S0129053389000068]
• 3: J. J. Dongarra , G. A. Geist , C. H. Romine, Fortran Subroutines for Computing the Eigenvalues and Eigenvectors of a General Matrix by Reduction to General Tridiagonal Form, University of Tennessee, Knoxville, TN, 1990
• 4: Jack J Dongarra , Eric Grosse, Distribution of mathematical software via electronic mail, Communications of the ACM, v.30 n.5, p.403-407, May 1987 [doi>10.1145/22899.22904]
• 5: DONGARRA, J. J., BUNCtt, J., MOLER, C., AND STEWART, G. LINPACK Users' Guzde SIAM, Philadelphia, 1979.
• 6: FRANcrs, J. G F. The QR transformation I, II. Computer J. 4 (1961), 265-271, 332 345.
• 7: GEIST, G. A Reduction of a general matrix to tridiagonal form. ORNL/TM-10091, Oak Ridge National Lab., 1989
• 8: GEIST, G. A., LIU, A., AND WACHSPRESS, E.L. Stabilized Gausslan reduction of an arbitrary matrix to tridlagonal form. ORNL/TM-11089, Oak Ridge National Lab., 1989.
• 9: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 10: GREGORY, R., AND KARNEY, D A Collection of Matrzces for Testing Computational Algorzthms. Wiley, New York, 1969.
• 11: HAAG, J. B., AND WATtiJNS, D.S. Hybrid chasing algorithms for the nonsymmetric matrix e~genvalue problem. Tech Rep TR 91-2, Dept of Mathematics, Washington State Umv., 1991.
• 12: SMn'H, B. T., BOYLE, J., DONOARRA, J., GARBOW, B., IKEBA, Y., KLEMA, V., AND MOLER, C. Matrix Ezgensystem Routines EISPACK Guide, 2nd ed., Springer-Verlag, New York, 1976.
• 13: STEWART, G.W. On efficient generation of random orthogonal matrices with an application to condition estimation. SIAM J. 2Vurner. Anal. 17 (1980), 403-409.
• 14: WATKINS, D.S. Understanding the QR algorithm, SIA~I Rev 24 (1982), 427-440.
• 15: David S. Watkins, Fundamentals of matrix computations, John Wiley & Sons, Inc., New York, NY, 1991
• 16: WATKINS, D. S., AND ELSNER, L Convergence of algorithms of decomposition type for the eigenvalue problem. Ltnear Algebra Appl. 143 (1991), 19-47
• 17: D. S. Watkins , L. Elsner, Chasing algorithms for the eigenvalues problem, SIAM Journal on Matrix Analysis and Applications, v.12 n.2, p.374-384, April 1991 [doi>10.1137/0612027]
• 18: J. H. Wilkinson, The algebraic eigenvalue problem, Oxford University Press, Inc., New York, NY, 1988

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Efficiency

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Eigenvalues and eigenvectors (direct and iterative methods)

General Terms:
Algorithms, Experimentation, Measurement, Performance, Verification

Keywords:
GR algorithm, LR algorithm, QR algorithm, chasing the bulge, eigenvalue, eigenvector