article

Block algorithms for reordering standard and generalized Schur forms

Author:

Daniel KressnerAuthors Info & Claims

ACM Transactions on Mathematical Software (TOMS), Volume 32, Issue 4

Pages 521 - 532

https://doi.org/10.1145/1186785.1186787

Published: 01 December 2006 Publication History

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]

Anderson, E., Bai, Z., Bischof, C. H., Blackford, S., Demmel, J. W., Dongarra, J. J., Du Croz, J., Greenbaum, A., Hammarling, S., McKenney, A., and Sorensen, D. C. 1999. LAPACK Users' Guide, 3rd ed. SIAM, Philadelphia, PA.

Digital Library

[2]

Bai, Z. and Demmel, J. W. 1993. On swapping diagonal blocks in real Schur form. Linear Algebra Appl. 186, 73--95.

[3]

Bai, Z. and Demmel, J. W. 1998. Using the matrix sign function to compute invariant subspaces. SIAM J. Matrix Anal. Appl. 19, 1, 205--225.

Digital Library

[4]

Bischof, C. H., Lang, B., and Sun, X. 2000. A framework for symmetric band reduction. ACM Trans. Math. Softw. 26, 4, 581--601.

Digital Library

[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]

Braman, K., Byers, R., and Mathias, R. 2002a. The multishift QR algorithm. I. Maintaining well-focused shifts and level 3 performance. SIAM J. Matrix Anal. Appl. 23, 4, 929--947.

Digital Library

[7]

Braman, K., Byers, R., and Mathias, R. 2002b. The multishift QR algorithm. II. Aggressive early deflation. SIAM J. Matrix Anal. Appl. 23, 4, 948--973.

Digital Library

[8]

Byers, R., He, C., and Mehrmann, V. 1997. The matrix sign function method and the computation of invariant subspaces. SIAM J. Matrix Anal. Appl. 18, 3, 615--632.

Digital Library

[9]

Dackland, K. and Kågström, B. 1999. Blocked algorithms and software for reduction of a regular matrix pair to generalized Schur form. ACM Trans. Math. Softw. 25, 4, 425--454.

Digital Library

[10]

Dongarra, J. J., Du Croz, J., Duff, I. S., and Hammarling, S. 1990. A set of level 3 basic linear algebra subprograms. ACM Trans. Math. Softw. 16, 1--17.

Digital Library

[11]

Fokkema, D. R., Sleijpen, G. L. G., and van der Vorst, H. A. 1998. Jacobi-Davidson style QR and QZ algorithms for the reduction of matrix pencils. SIAM J. Sci. Comput. 20, 1, 94--125.

Digital Library

[12]

Golub, G. H. and Van Loan, C. F. 1996. Matrix Computations, 3rd ed. Johns Hopkins University Press, Baltimore, MD.

Digital Library

[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]

Kågström, B. and Poromaa, P. 1996b. LAPACK-Style algorithms and software for solving the generalized Sylvester equation and estimating the separation between regular matrix pairs. ACM Trans. Math. Softw. 22, 1, 78--103.

Digital Library

[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]

Sleijpen, G. L. G. and van der Vorst, H. A. 1996. A Jacobi-Davidson iteration method for linear eigenvalue problems. SIAM J. Matrix Anal. Appl. 17, 2, 401--425.

Digital Library

[21]

Stewart, G. W. 1976. Algorithm 407: HQR3 and EXCHNG: FORTRAN programs for calculating the eigenvalues of a real upper Hessenberg matrix in a prescribed order. ACM Trans. Math. Softw. 2, 275--280.

Digital Library

[22]

Stewart, G. W. 2002. A Krylov-Schur algorithm for large eigenproblems. SIAM J. Matrix Anal. Appl. 23, 3, 601--614.

Digital Library

[23]

Van Dooren, P. 1982. Algorithm 590: DSUBSP and EXCHQZ: Fortran subroutines for computing deflating subspaces with specified spectrum. ACM Trans. Math. Softw. 8, 376--382.

Digital Library

[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.

Cited By

Benzi MRinelli MSimunec I(2023)Computation of the von Neumann entropy of large matrices via trace estimators and rational Krylov methodsNumerische Mathematik10.1007/s00211-023-01368-6155:3-4(377-414)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1007/s00211-023-01368-6
Massei SRobol L(2022)Mixed Precision Recursive Block Diagonalization for Bivariate Functions of MatricesSIAM Journal on Matrix Analysis and Applications10.1137/21M140787243:2(638-660)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1137/21M1407872
Myllykoski MKjelgaard Mikkelsen C(2020)Task‐based, GPU‐accelerated and robust library for solving dense nonsymmetric eigenvalue problemsConcurrency and Computation: Practice and Experience10.1002/cpe.591533:11Online publication date: 6-Aug-2020
https://doi.org/10.1002/cpe.5915
Show More Cited By

Index Terms

Block algorithms for reordering standard and generalized Schur forms
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Computations on matrices

Recommendations

Projected nonsymmetric algebraic Riccati equations and refining estimates of invariant and deflating subspaces

We consider the numerical solution of the projected nonsymmetric algebraic Riccati equations or their associated Sylvester equations via Newton's method, arising in the refinement of estimates of invariant (or deflating subspaces) for a large and sparse ...
Jacobi--Davidson Style QR and QZ Algorithms for the Reduction of Matrix Pencils

Recently the Jacobi--Davidson subspace iteration method has been introduced as a new powerful technique for solving a variety of eigenproblems. In this paper we will further exploit this method and enhance it with several techniques so that practical and ...
Refining estimates of invariant and deflating subspaces for large and sparse matrices and pencils
Abstract
We consider the refinement of estimates of invariant (or deflating) subspaces for a large and sparse real matrix (or pencil) in $$\mathbb {R}^{n \times n}$$, through some (generalized) nonsymmetric algebraic Riccati equations or their associated (...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Mathematical Software

ACM Transactions on Mathematical Software Volume 32, Issue 4

December 2006

145 pages

ISSN:0098-3500

EISSN:1557-7295

DOI:10.1145/1186785

Issue’s Table of Contents

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 2006

Published in TOMS Volume 32, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
522
Total Downloads

Downloads (Last 12 months)42
Downloads (Last 6 weeks)5

Reflects downloads up to 22 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Benzi MRinelli MSimunec I(2023)Computation of the von Neumann entropy of large matrices via trace estimators and rational Krylov methodsNumerische Mathematik10.1007/s00211-023-01368-6155:3-4(377-414)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1007/s00211-023-01368-6
Massei SRobol L(2022)Mixed Precision Recursive Block Diagonalization for Bivariate Functions of MatricesSIAM Journal on Matrix Analysis and Applications10.1137/21M140787243:2(638-660)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1137/21M1407872
Myllykoski MKjelgaard Mikkelsen C(2020)Task‐based, GPU‐accelerated and robust library for solving dense nonsymmetric eigenvalue problemsConcurrency and Computation: Practice and Experience10.1002/cpe.591533:11Online publication date: 6-Aug-2020
https://doi.org/10.1002/cpe.5915
Hoffman NSchwartz OToledo S(2018)Efficient Evaluation of Matrix PolynomialsParallel Processing and Applied Mathematics10.1007/978-3-319-78024-5_3(24-35)Online publication date: 23-Mar-2018
https://doi.org/10.1007/978-3-319-78024-5_3
Myllykoski M(2018)A Task-Based Algorithm for Reordering the Eigenvalues of a Matrix in Real Schur FormParallel Processing and Applied Mathematics10.1007/978-3-319-78024-5_19(207-216)Online publication date: 23-Mar-2018
https://doi.org/10.1007/978-3-319-78024-5_19
Stotland VSchwartz OToledo S(2017)High‐performance direct algorithms for computing the sign function of triangular matricesNumerical Linear Algebra with Applications10.1002/nla.213925:2Online publication date: 19-Dec-2017
https://doi.org/10.1002/nla.2139
Berljafa MGüttel S(2015)Generalized Rational Krylov Decompositions with an Application to Rational ApproximationSIAM Journal on Matrix Analysis and Applications10.1137/14099808136:2(894-916)Online publication date: Jan-2015
https://doi.org/10.1137/140998081
Romero ERoman J(2014)A parallel implementation of Davidson methods for large-scale eigenvalue problems in SLEPcACM Transactions on Mathematical Software10.1145/254369640:2(1-29)Online publication date: 5-Mar-2014
https://dl.acm.org/doi/10.1145/2543696
Granat RKågström BKressner D(2010)A Novel Parallel QR Algorithm for Hybrid Distributed Memory HPC SystemsSIAM Journal on Scientific Computing10.1137/09075693432:4(2345-2378)Online publication date: 1-Aug-2010
https://dl.acm.org/doi/10.1137/090756934
Granat RKågström BKressner D(2009)Parallel eigenvalue reordering in real Schur formsConcurrency and Computation: Practice and Experience10.1002/cpe.138621:9(1225-1250)Online publication date: 11-Feb-2009
https://doi.org/10.1002/cpe.1386
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents