Blocked algorithms and software for reduction of a regular matrix pair to generalized Schur form

ABSTRACT

A two-stage blocked algorithm for reduction of a regular matrix pair (A , B ) to upper Hessenberg-triangular form is presented. In stage 1 (A, B is reduced to block upper Hessenberg-triangular form using mainly level 3 (matrix-matrix) operations that permit data reuse in the higher levels of a memory hierarchy. In the second stage all but one of the r subdiagonals of the block Hessenberg A-part are set to zero using Givens rotations. The algorithm proceeds in a sequence of supersweeps, each reducing m columns. The updates with respect to row and column rotations are organized to reference consecutive columns of A and B. To further improve the data locality, all rotations produced in a supersweep are stored to enable a left-looking reference pattern, i.e., all updates are delayed until they are required for the continuation of the supersweep. Moreover, we present a blocked variant of the single-diagonal double-shift QZ method for computing the generalized Schur form of (A, B in upper Hessenberg-triangular form. The blocking for improved data locality is done similarly, now by restructuring the reference pattern of the updates associated with the bulge chasing in the QZ iteration. Timing results show that our new blocked variants outperform the current LAPACK routines, including drivers for the generalized eigenvalue problem, by a factor 2-5 for sufficiently large problems.

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: E. Anderson , J. Dongarra , S. Ostrouchov, LAPACK Working Note 41: Installation Guide for LAPACK, University of Tennessee, Knoxville, TN, 1992
• 3: 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]
• 4: Michael W. Berry , Jack J. Dongarra , Youngbae Kim, A parallel algorithm for the reduction of a nonsymmetric matrix to block upper-Hessenberg form, Parallel Computing, v.21 n.8, p.1189-1211, Aug. 1995 [doi>10.1016/0167-8191(95)00015-G ]
• 5: Christian Bischof , Charles van Loan, The WY representation for products of householder matrices, SIAM Journal on Scientific and Statistical Computing, v.8 n.1, p.2-13, January 2, 1987 [doi>10.1137/0908009]
• 6: BISCHOF, C. H., LANG, B., AND SUN, X. 1996. A framework for symmetric band reduction. Tech. Rep., Preprint BUGHW-SC-96/3. Fachbereich Mathematik, Bergische Universit t, Wuppertal, Germany.
• 7: 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
• 8: DACKLAND, K. 1998. Parallel reduction of a regular matrix pair to block Hessenbergtriangular form--Algorithm design and performance modeling. Tech. Rep. UMINF-98.09. Department of Computing Science, Ume University, Ume , Sweden.
• 9: Krister Dackland , Bo Kågström, Reduction of a Regular Matrix Pair (A, B) to Block Hessenberg Triangular Form, Proceedings of the Second International Workshop on Applied Parallel Computing, Computations in Physics, Chemistry and Engineering Science, p.125-133, August 21-24, 1995
• 10: Krister Dackland , Bo Kågström, A Hierarchical Approach for Performance Analysis of ScaLAPACK-Based Routines Using the Distributed Linear Algebra Machine, Proceedings of the Third International Workshop on Applied Parallel Computing, Industrial Computation and Optimization, p.186-195, August 18-21, 1996
• 11: Krister Dackland , Bo Kågström, A ScaLAPACK-Style Algorithm for Reducing a Regular Matrix Pair to Block Hessenberg-Triangular Form, Proceedings of the 4th International Workshop on Applied Parallel Computing, Large Scale Scientific and Industrial Problems, p.95-103, June 14-17, 1998
• 12: J. J. Dongarra , Jermey Du Cruz , Sven Hammerling , I. S. Duff, Algorithm 679; a set of level 3 basic linear algebra subprograms: model implementation and test programs, ACM Transactions on Mathematical Software (TOMS), v.16 n.1, p.18-28, March 1990 [doi>10.1145/77626.77627]
• 13: DUBRULLE, A.A. 1991. The multishift QR algorithm: Is it worth the trouble?. Tech. Rep. G320-3558+. Palo Alto Scientific Center, IBM Corp., Palo Alto, CA.
• 14: DUBRULLE, A. A. AND GOLUB, G. H. 1994. A multishift QR algorithm without computation of the shifts. Num. Alg. 7, 173-181.
• 15: ENRIGHT, W. AND SERBIN, S. 1978. A note on the efficient solution of matrix pencil systems. BIT 18, 276-281.
• 16: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 17: Greg Henry , David Watkins , Jack Dongarra, Parallel Implementation of the Nonsymmetric QR Algorithm forDistributed Memory Architectures, University of Tennessee, Knoxville, TN, 1997
• 18: Bo Kågström , Per Ling , Charles van Loan, GEMM-based level 3 BLAS: high-performance model implementations and performance evaluation benchmark, ACM Transactions on Mathematical Software (TOMS), v.24 n.3, p.268-302, Sept. 1998 [doi>10.1145/292395.292412]
• 19: Bo Kågström , Charles van Loan, Algorithm 784: GEMM-based level 3 BLAS: portability and optimization issues, ACM Transactions on Mathematical Software (TOMS), v.24 n.3, p.303-316, Sept. 1998 [doi>10.1145/292395.292426]
• 20: Bruno Lang, A parallel algorithm for reducing symmetric banded matrices to tridiagonal form, SIAM Journal on Scientific Computing, v.14 n.6, p.1320-1338, Nov. 1993 [doi>10.1137/0914078]
• 21: LANG, B. 1998a. Efficient eigenvalue and singular value computations on shared memory machines. Tech. Rep. BUGHW-SC 98/4. Fachbereich Mathematik, Bergische Universit t, Wuppertal, Germany.
• 22: Bruno Lang, Using Level 3 BLAS in Rotation-Based Algorithms, SIAM Journal on Scientific Computing, v.19 n.2, p.626-634, March 1998 [doi>10.1137/S1064827595280211]
• 23: MOLER, C. B. AND STEWART, G.W. 1973. An algorithm for generalized matrix eigenvalue problems. SIAM J. Numer. Anal. 10, 2, 241-256.
• 24: Robert Schreiber , Charles van Loan, A storage-efficient WY representation for products of householder transformations, SIAM Journal on Scientific and Statistical Computing, v.10 n.1, p.53-57, January 1989 [doi>10.1137/0910005]
• 25: 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]
• 26: David S. Watkins, Bulge Exchanges in Algorithms of QR Type, SIAM Journal on Matrix Analysis and Applications, v.19 n.4, p.1074-1096, Oct. 1998 [doi>10.1137/S0895479896299950]
• 27: David Watkins , Ludwig Elsner, Theory of Decomposition and Bulge-Chasing Algorithms for the Generalized Eigenvalue Problem, SIAM Journal on Matrix Analysis and Applications, v.15 n.3, p.943-967, July 1994 [doi>10.1137/S089547989122377X]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

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

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Certification and testing; Efficiency; Reliability and robustness; Portability**

General Terms:
Algorithms

Keywords:
QZ-algorithm, Hessenberg-triangular reduction, LAPACK, blocked algorithms, generalized Schur form, memory hierarchy, parallelization