Block algorithms for reordering standard and generalized Schur forms

ABSTRACT

Block algorithms for reordering a selected set of eigenvalues in a standard or generalized Schur form are proposed. Efficiency is achieved by delaying orthogonal transformations and (optionally) making use of level 3 BLAS operations. Numerical experiments demonstrate that existing algorithms, as currently implemented in LAPACK, are outperformed by up to a factor of four.

REFERENCES

• 1: E. Anderson , Z. Bai , C. Bischof , L. S. Blackford , J. Demmel , Jack J. Dongarra , J. Du Croz , S. Hammarling , A. Greenbaum , A. McKenney , D. Sorensen, LAPACK Users' guide (third ed.), Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999
• 2: Bai, Z. and Demmel, J. W. 1993. On swapping diagonal blocks in real Schur form. Linear Algebra Appl. 186, 73--95.
• 3: Zhaojun Bai , James Demmel, Using the Matrix Sign Function to Compute Invariant Subspaces, SIAM Journal on Matrix Analysis and Applications, v.19 n.1, p.205-225, Jan., 1998 [doi>10.1137/S0895479896297719]
• 4: Christian H. Bischof , Bruno Lang , Xiaobai Sun, A framework for symmetric band reduction, ACM Transactions on Mathematical Software (TOMS), v.26 n.4, p.581-601, Dec. 2000 [doi>10.1145/365723.365735]
• 5: Bojanczyk, A. and Van Dooren, P. 1993. Reordering diagonal blocks in the real Schur form. In Linear Algebra for Large Scale and Real-Time Applications, M. S. Moonen et al., Eds. Kluwer Academic, Dordrecht, the Netherlands, 351--352.
• 6: Karen Braman , Ralph Byers , Roy Mathias, The Multishift QR Algorithm. Part I: Maintaining Well-Focused Shifts and Level 3 Performance, SIAM Journal on Matrix Analysis and Applications, v.23 n.4, p.929-947, 2001 [doi>10.1137/S0895479801384573]
• 7: Karen Braman , Ralph Byers , Roy Mathias, The Multishift QR Algorithm. Part II: Aggressive Early Deflation, SIAM Journal on Matrix Analysis and Applications, v.23 n.4, p.948-973, 2001 [doi>10.1137/S0895479801384585]
• 8: Ralph Byers , Chunyang He , Volker Mehrmann, The Matrix Sign Function Method and the Computation of Invariant Subspaces, SIAM Journal on Matrix Analysis and Applications, v.18 n.3, p.615-632, July 1997 [doi>10.1137/S0895479894277454]
• 9: Krister Dackland , Bo Kågström, Blocked algorithms and software for reduction of a regular matrix pair to generalized Schur form, ACM Transactions on Mathematical Software (TOMS), v.25 n.4, p.425-454, Dec. 1999 [doi>10.1145/332242.332244]
• 10: J. J. Dongarra , Jeremy Du Croz , Sven Hammarling , I. S. Duff, A set of level 3 basic linear algebra subprograms, ACM Transactions on Mathematical Software (TOMS), v.16 n.1, p.1-17, March 1990 [doi>10.1145/77626.79170]
• 11: Diederik R. Fokkema , Gerard L. G. Sleijpen , Henk A. Van der, Jacobi--Davidson Style QR and QZ Algorithms for the Reduction of Matrix Pencils, SIAM Journal on Scientific Computing, v.20 n.1, p.94-125, Aug. 1998 [doi>10.1137/S1064827596300073]
• 12: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 13: Kågström, B. 1993. A direct method for reordering eigenvalues in the generalized real Schur form of a regular matrix pair (A, B). In Linear Algebra for Large Scale and Real-Time Applications, M. S. Moonen et al., Eds. Kluwer Academic, Dordrecht, the Netherlands, 195--218.
• 14: Kåöm, B. and Kressner, D. 2005. Multishift variants of the QZ algorithm with aggressive early deflation. Tech. Rep. UMINF-05. 11, Department of Computing Science, Umeå University, Umeå, Sweden.
• 15: Kåöm, B. and Poromaa, P. 1996a. Computing eigenspaces with specified eigenvalues of a regular matrix pari (A, B) and condition estimation: Theory, algorithms and software. Numer. Algorithms 12, 3-4, 369--407
• 16: Bo Kågström , Peter Poromaa, LAPACK-style algorithms and software for solving the generalized Sylvester equation and estimating the separation between regular matrix pairs, ACM Transactions on Mathematical Software (TOMS), v.22 n.1, p.78-103, March 1996 [doi>10.1145/225545.225552]
• 17: Kressner, D. 2004. Numerical methods and software for general and structured eigenvalue problems. Ph.D. thesis, TU Berlin, Institut für Mathematik, Berlin, Germany.
• 18: Lang, B. 1997. Effiziente Orthogonaltransformationen bei der Eigen- und Singulärwertzer- legung. Habilitationsschrift.
• 19: Murnaghan, F. D. and Wintner, A. 1931. A canonical form for real matrices under orthogonal transformations. Proc. Natl. Acad. Sci. USA 17, 417--420.
• 20: Gerard L. G. Sleijpen , Henk A. Van der, A Jacobi--Davidson Iteration Method for Linear EigenvalueProblems, SIAM Journal on Matrix Analysis and Applications, v.17 n.2, p.401-425, April 1996 [doi>10.1137/S0895479894270427]
• 21: G. W. Stewart, Algorithm 506: HQR3 and EXCHNG: Fortran Subroutines for Calculating and Ordering the Eigenvalues of a Real Upper Hessenberg Matrix [F2], ACM Transactions on Mathematical Software (TOMS), v.2 n.3, p.275-280, Sept. 1976 [doi>10.1145/355694.355700]
• 22: G. W. Stewart, A Krylov--Schur Algorithm for Large Eigenproblems, SIAM Journal on Matrix Analysis and Applications, v.23 n.3, p.601-614, 2001 [doi>10.1137/S0895479800371529]
• 23: P. Van Dooren, Algorithm 590: DSUBSP and EXCHQZ: FORTRAN Subroutines for Computing Deflating Subspaces with Specified Spectrum, ACM Transactions on Mathematical Software (TOMS), v.8 n.4, p.376-382, Dec. 1982 [doi>10.1145/356012.356017]
• 24: Whaley, R. C., Petitet, A., and Dongarra, J. J. 2001. Automated empirical optimization of software and the ATLAS project. Parallel Comput. 27, 1--2, 3--35.

INDEX TERMS

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

Additional Classification:
  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, Performance

Keywords:
Schur form, deflating subspace, invariant subspace, reordering