Algorithm 826: A parallel eigenvalue routine for complex Hessenberg matrices

ABSTRACT

A code for computing the eigenvalues of a complex Hessenberg matrix is presented. This code computes the Schur decomposition of a complex Hessenberg matrix. Together with existing ScaLAPACK routines, the eigenvalues of dense complex matrices can be directly computed using a parallel QR algorithm.This parallel complex Schur decomposition routine was developed to fill a void in the ScaLAPACK library and was based on the parallel real Schur decomposition routine already in ScaLAPACK. The real-arithmetic version was appropriately modified to make it work with complex arithmetic and implement a complex multiple bulge QR algorithm. This also required the development of new auxiliary routines that perform essential operations for the complex Schur decomposition, and that will provide additional linear algebra computation capability to the parallel numerical library community.

REFERENCES

• 1: 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]
• 2: Michael W. Berry , Jack J. Dongarra , Youngbae Kim, LAPACK Working Note 68: A Parallel Algorithm for the Reduction of a Nonsymmetric Matrix to Block Upper-Hessenberg Form, University of Tennessee, Knoxville, TN, 1994
• 3: Jack J. Dongarra , L. S. Blackford , J. Choi , A. Cleary , E. D'Azeuedo , J. Demmel , I. Dhillon , S. Hammarling , G. Henry , A. Petitet , K. Stanley , D. Walker , R. C. Whaley, ScaLAPACK user's guide, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997
• 4: Choi, J., Demmel, J., Dhillon, I., Dongarra, J., Ostrouchov, S., Petitet, A., Stanley, K., Walker, D., and Whaley, R. C. 1995. Installation guide for ScaLAPACK. Computer Sciences Dept. Tech. Rep. CS-95-280 (Mar.), University of Tennessee, Knoxville, TN. LAPACK Working Note #93.
• 5: Dongarra, J. J. and Van de Geijn, R. 1992. Reduction to condensed form on distributed memory architectures. Parallel Computing 18, 973--982.
• 6: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 7: Greg Henry , David Watkins , Jack Dongarra, Parallel Implementation of the Nonsymmetric QR Algorithm forDistributed Memory Architectures, University of Tennessee, Knoxville, TN, 1997
• 8: R. B. Lehoucq, LAPACK Working Note 72: The Computation of Elementary Unitary Matrices, University of Tennessee, Knoxville, TN, 1994
• 9: David S. Watkins, Fundamentals of matrix computations, John Wiley & Sons, Inc., New York, NY, 1991
• 10: David S. Watkins, Shifting strategies for the parallel QR algorithm, SIAM Journal on Scientific Computing, v.15 n.4, p.953-958, July 1994 [doi>10.1137/0915057]
• 11: Watkins, D. S. and Elsner, L. 1991. Convergence of algorithms of decomposition type for the eigenvalue problem. Lin. Alg. Appl. 143, 19--47.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Distributed programming

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

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

General Terms:
Design, Performance

Keywords:
Parallel programming, ScaLAPACK, complex matrices, eigenvalue, parallel QR algorithm, schur decomposition