article

Algorithm 854: Fortran 77 subroutines for computing the eigenvalues of Hamiltonian matrices II

Authors:

Daniel KressnerAuthors Info & Claims

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

Pages 352 - 373

https://doi.org/10.1145/1141885.1141895

Published: 01 June 2006 Publication History

Abstract

This article describes Fortran 77 subroutines for computing eigenvalues and invariant subspaces of Hamiltonian and skew-Hamiltonian matrices. The implemented algorithms are based on orthogonal symplectic decompositions, implying numerical backward stability as well as symmetry preservation for the computed eigenvalues. These algorithms are supplemented with balancing and block algorithms which can lead to considerable accuracy and performance improvements. As a by-product, an efficient implementation for computing symplectic QR decompositions is provided. We demonstrate the usefulness of the subroutines for several, practically relevant examples.

Supplementary Material

ZIP File (854.zip)

Software for "Fortran 77 subroutines for computing the eigenvalues of Hamiltonian matrices II"

Download
211.63 KB

References

[1]

Abels, J. and Benner, P. 1999. CAREX---a collection of benchmark examples for continuous-time algebraic Riccati equations (version 2.0). SLICOT working note 1999-14, http://www.win.tue.nl/niconet.

[2]

Anderson, E., Bai, Z., Bischof, C., 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.

[3]

Arnold, III, W. and Laub, A. 1984. Generalized eigenproblem algorithms and software for algebraic Riccati equations. Proceedings of the IEEE 72, 1746--1754.

[4]

Bai, Z. and Demmel, J. W. 1989. On a block implementation of the Hessenberg multishift QR iterations. Internat. J. High Speed Comput. 1, 97--112.

[5]

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

[6]

Benner, P. 2000. Symplectic balancing of Hamiltonian matrices. SIAM J. Sci. Comput. 22, 5, 1885--1904.

[7]

Benner, P., Byers, R., and Barth, E. 2000. Algorithm 800: Fortran 77 subroutines for computing the eigenvalues of Hamiltonian matrices I: The square-reduced method. ACM Trans. Math. Soft. 26, 49--77.

[8]

Benner, P., Byers, R., Mehrmann, V., and Xu, H. 2004. Robust numerical methods for robust control. Preprint 2004-06, Institut für Mathematik, TU Berlin, D-10623 Berlin, Germany. http://www.math.tu-berlin.de/preprints.

[9]

Benner, P. and Kressner, D. 2003. Balancing sparse Hamiltonian eigenproblems. Linear Algebra Appl. To appear.

[10]

Benner, P., Kressner, D., and Mehrmann, V. 2003. Structure preservation: A challenge in computational control. Future Generation Comput. Syst. 19, 7, 1243--1252.

[11]

Benner, P., Kressner, D., and Mehrmann, V. 2005. Skew-Hamiltonian and Hamiltonian eigenvalue problems: Theory, algorithms and applications. In Proceedings of the Conference on Applied Mathematics and Scientific Computing. Brijoni, Croatia. Z. Drmae, M. Marusic, and Z. Tutek, Eds. Springer-Verlag, 3--39.

[12]

Benner, P., Mehrmann, V., Sima, V., Van Huffel, S., and Varga, A. 1999. SLICOT---a subroutine library in systems and control theory. In Applied and Computational Control, Signals, and Circuits, Vol. 1. Birkhäuser, Boston, MA, 499--539.

[13]

Benner, P., Mehrmann, V., and Xu, H. 1997. A new method for computing the stable invariant subspace of a real Hamiltonian matrix. J. Comput. Appl. Math. 86, 17--43.

[14]

Benner, P., Mehrmann, V., and Xu, H. 1998. A numerically stable, structure preserving method for computing the eigenvalues of real Hamiltonian or symplectic pencils. Numerische Mathematik 78, 3, 329--358.

[15]

Benner, P., Mehrmann, V., and Xu, H. 1999. A note on the numerical solution of complex Hamiltonian and skew-Hamiltonian eigenvalue problems. Electron. Trans. Numer. Anal. 8, 115--126.

[16]

Bischof, C. and Van Loan, C. F. 1987. The WY representation for products of Householder matrices. SIAM J. Sci. Statist. Comput. 8, 1, 2--13.

[17]

Bojanczyk, A., Golub, G. H., and Van Dooren, P. 1992. The periodic Schur decomposition; algorithm and applications. In Advanced Signal Processing Algorithms, Architectures, and Implementations III. Vol. 1770. SPIE, the International Society for Optical Engineering, Bellingham, WA, 31--42.

[18]

Boyd, S., Balakrishnan, V., and Kabamba, P. 1989. A bisection method for computing the H∞ norm of a transfer matrix and related problems. Math. Control, Signals, Syst. 2, 207--219.

[19]

Bunch, J. R. 1987. The weak and strong stability of algorithms in numerical linear algebra. Linear Algebra Appl. 88/89, 49--66.

[20]

Bunse-Gerstner, A. 1986. Matrix factorizations for symplectic QR-like methods. Linear Algebra Appl. 83, 49--77.

[21]

Burke, J. V., Lewis, A. S., and Overton, M. L. 2003. Robust stability and a criss-cross algorithm for pseudospectra. IMA J. Numer. Anal. 23, 3, 359--375.

[22]

Byers, R. 1983. Hamiltonian and symplectic algorithms for the algebraic Riccati equation. Ph.D. thesis, Department of Computer Science, Cornell University, Ithaca, NY.

[23]

Byers, R. 1988. A bisection method for measuring the distance of a stable to unstable matrices. SIAM J. Sci. Statist. Comput. 9, 875--881.

[24]

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.

[25]

Dongarra, J. J., Sorensen, D. C., and Hammarling, S. J. 1989. Block reduction of matrices to condensed forms for eigenvalue computations. J. Comput. Appl. Math. 27, 1-2, 215--227. (Reprinted in Parallel Algorithms for Numerical Linear Algebra, 215--227, North-Holland, Amsterdam, 1990.)

[26]

Dubrulle, A. A. 1991. The multishift QR algorithm--is it worth the trouble? TR 6320-3558, IBM Scientific Center, Palo Alto, CA.

[27]

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

[28]

Hench, J. J. and Laub, A. J. 1994. Numerical solution of the discrete-time periodic Riccati equation. IEEE Trans. Automat. Control 39, 6, 1197--1210.

[29]

Hwang, T.-M., Lin, W.-W., and Mehrmann, V. 2003. Numerical solution of quadratic eigenvalue problems with structure-preserving methods. SIAM J. Sci. Comput. 24, 4, 1283--1302.

[30]

Kressner, D. 2003a. Block algorithms for orthogonal symplectic factorizations. BIT 43, 4, 775--790.

[31]

Kressner, D. 2003b. The periodic QR algorithm is a disguised QR algorithm. Linear Algebra Appl. To appear.

[32]

Kressner, D. 2004. Numerical methods and software for general and structured eigenvalue problems. Ph.D. thesis, TU Berlin, Institut für Mathematik, Berlin, Germany.

[33]

Lancaster, P. and Rodman, L. 1995. Algebraic Riccati Equations. Oxford University Press, Oxford, UK.

[34]

Leimkuhler, B. J. and Van Vleck, E. S. 1997. Orthosymplectic integration of linear Hamiltonian systems. Numer. Math. 77, 2, 269--282.

[35]

Mehrmann, V. and Watkins, D. S. 2000. Structure-preserving methods for computing eigenpairs of large sparse skew-Hamiltonian/Hamiltonian pencils. SIAM J. Sci. Comput. 22, 6, 1905--1925.

[36]

Osborne, E. E. 1960. On preconditioning of matrices. J. ACM 7, 338--345.

[37]

Parlett, B. N. and Reinsch, C. 1969. Balancing a matrix for calculation of eigenvalues and eigenvectors. Numerische Mathematik 13, 293--304.

[38]

Schreiber, R. and Van Loan, C. F. 1989. A storage-efficient WY representation for products of Householder transformations. SIAM J. Sci. Statist. Comput. 10, 1, 53--57.

[39]

Stefanovski, J. and Trenčevski, K. 1998. Antisymmetric Riccati matrix equation. In 1st Congress of the Mathematicians and Computer Scientists of Macedonia (Ohrid'96). Sojuz. Mat. Inform. Maked., Skopje, 83--92.

[40]

The MathWorks, Inc. 2002. Matlab Version 6.5. The MathWorks, Inc., Natick, MA.

[41]

The Working Group on Software (WGS) 1996. SLICOT Implementation and Documentation Standards 2.1. The Working Group on Software (WGS), WGS-report 96-1. http://www.win.tue.nl/wgs/reports.html.

[42]

Tisseur, F. and Meerbergen, K. 2001. The quadratic eigenvalue problem. SIAM Rev. 43, 2, 235--286.

[43]

Van Loan, C. F. 1975. A general matrix eigenvalue algorithm. SIAM J. Numer. Anal. 12, 6, 819--834.

[44]

Van Loan, C. F. 1984. A symplectic method for approximating all the eigenvalues of a Hamiltonian matrix. Linear Algebra Appl. 61, 233--251.

[45]

Watkins, D. S. 1996. The transmission of shifts and shift blurring in the QR algorithm. Linear Algebra Appl. 241--243, 877--896.

[46]

Wilkinson, J. H. and Reinsch, C. 1971. Handbook for Automatic Computation. Vol. II Linear Algebra. Springer-Verlag, New York, NY.

[47]

Xu, H. and Lu, L. Z. 1995. Properties of a quadratic matrix equation and the solution of the continuous-time algebraic Riccati equation. Linear Algebra Appl. 222, 127--145.

[48]

Zhou, K., Doyle, J. C., and Glover, K. 1996. Robust and Optimal Control. Prentice-Hall, Upper Saddle River, NJ.

Cited By

Benner PFaßbender HYang C(2018)Some remarks on the complex J-symmetric eigenproblemLinear Algebra and its Applications10.1016/j.laa.2018.01.014544(407-442)Online publication date: May-2018
https://doi.org/10.1016/j.laa.2018.01.014
Shiozaki T(2016)An efficient solver for large structured eigenvalue problems in relativistic quantum chemistryMolecular Physics10.1080/00268976.2016.1158423115:1-2(5-12)Online publication date: 11-Mar-2016
https://doi.org/10.1080/00268976.2016.1158423
Benner P(2015)Theory and Numerical Solution of Differential and Algebraic Riccati EquationsNumerical Algebra, Matrix Theory, Differential-Algebraic Equations and Control Theory10.1007/978-3-319-15260-8_4(67-105)Online publication date: 2015
https://doi.org/10.1007/978-3-319-15260-8_4
Show More Cited By

Index Terms

Algorithm 854: Fortran 77 subroutines for computing the eigenvalues of Hamiltonian matrices II
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Computations on matrices
  2. Mathematical software
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types

Recommendations

Algorithm 800: Fortran 77 subroutines for computing the eigenvalues of Hamiltonian matrices. I: the square-reduced method

This article describes LAPACK-based Fortran 77 subroutines for the reduction of a Hamiltonian matrix to square-reduced form and the approximation of all its eigenvalues using the implicit version of Van Loan's method. The transformation of the ...
Numerical Computation of Deflating Subspaces of Skew-Hamiltonian/Hamiltonian Pencils

We discuss the numerical solution of structured generalized eigenvalue problems that arise from linear-quadratic optimal control problems, $H_{\infty}$ optimization, multibody systems, and many other areas of applied mathematics, physics, and chemistry. ...
Note on structured indefinite perturbations to Hermitian matrices

In a recent paper, Overton and Van Dooren have considered structured indefinite perturbations to a given Hermitian matrix. We extend their results to skew-Hermitian, Hamiltonian and skew-Hamiltonian matrices. As an application, we give a formula for ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Mathematical Software

ACM Transactions on Mathematical Software Volume 32, Issue 2

June 2006

205 pages

ISSN:0098-3500

EISSN:1557-7295

DOI:10.1145/1141885

Issue’s Table of Contents

Copyright © 2006 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 2006

Published in TOMS Volume 32, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
716
Total Downloads

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

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Benner PFaßbender HYang C(2018)Some remarks on the complex J-symmetric eigenproblemLinear Algebra and its Applications10.1016/j.laa.2018.01.014544(407-442)Online publication date: May-2018
https://doi.org/10.1016/j.laa.2018.01.014
Shiozaki T(2016)An efficient solver for large structured eigenvalue problems in relativistic quantum chemistryMolecular Physics10.1080/00268976.2016.1158423115:1-2(5-12)Online publication date: 11-Mar-2016
https://doi.org/10.1080/00268976.2016.1158423
Benner P(2015)Theory and Numerical Solution of Differential and Algebraic Riccati EquationsNumerical Algebra, Matrix Theory, Differential-Algebraic Equations and Control Theory10.1007/978-3-319-15260-8_4(67-105)Online publication date: 2015
https://doi.org/10.1007/978-3-319-15260-8_4
Kressner DVoigt M(2015)Distance Problems for Linear Dynamical SystemsNumerical Algebra, Matrix Theory, Differential-Algebraic Equations and Control Theory10.1007/978-3-319-15260-8_20(559-583)Online publication date: 2015
https://doi.org/10.1007/978-3-319-15260-8_20
Grivet‐Talocia SGustavsen B(2015)BibliographyPassive Macromodeling10.1002/9781119140931.biblio(839-862)Online publication date: 6-Nov-2015
https://doi.org/10.1002/9781119140931.biblio
Freitag MSpence A(2014)A new approach for calculating the real stability radiusBIT10.1007/s10543-013-0457-x54:2(381-400)Online publication date: 1-Jun-2014
https://dl.acm.org/doi/10.1007/s10543-013-0457-x
Madhusudhanan ACorno MBonsen BHolweg E(2012)Solving Algebraic Riccati Equation real time for Integrated Vehicle Dynamics Control2012 American Control Conference (ACC)10.1109/ACC.2012.6314669(3593-3598)Online publication date: Jun-2012
https://doi.org/10.1109/ACC.2012.6314669
Mehrmann VSchröder CSimoncini V(2012)An implicitly-restarted Krylov subspace method for real symmetric/skew-symmetric eigenproblemsLinear Algebra and its Applications10.1016/j.laa.2009.11.009436:10(4070-4087)Online publication date: May-2012
https://doi.org/10.1016/j.laa.2009.11.009
Benner PFaßbender HStoll M(2011)A Hamiltonian Krylov–Schur-type method based on the symplectic Lanczos processLinear Algebra and its Applications10.1016/j.laa.2010.04.048435:3(578-600)Online publication date: Aug-2011
https://doi.org/10.1016/j.laa.2010.04.048
Maehara TMurota K(2010)A numerical algorithm for block-diagonal decomposition of matrix *-algebras with general irreducible componentsJapan Journal of Industrial and Applied Mathematics10.1007/s13160-010-0007-827:2(263-293)Online publication date: 13-May-2010
https://doi.org/10.1007/s13160-010-0007-8
Show More Cited By

View Options

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.

Figures

Tables

Media

View Issue’s Table of Contents