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

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.

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: 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
• 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: 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]
• 5: Bai, Z. and Demmel, J. W. 1993. On swapping diagonal blocks in real Schur form. Linear Algebra Appl. 186, 73--95.
• 6: Peter Benner, Symplectic Balancing of Hamiltonian Matrices, SIAM Journal on Scientific Computing, v.22 n.5, p.1885-1904, 2000 [doi>10.1137/S1064827500367993]
• 7: Peter Benner , Ralph Byers , Eric Barth, Algorithm 800: Fortran 77 subroutines for computing the eigenvalues of Hamiltonian matrices. I: the square-reduced method, ACM Transactions on Mathematical Software (TOMS), v.26 n.1, p.49-77, March 2000 [doi>10.1145/347837.347852]
• 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: Peter Benner , Daniel Kressner , Volker Mehrmann, Structure preservation: a challenge in computational control, Future Generation Computer Systems, v.19 n.7, p.1243-1252, October 2003 [doi>10.1016/S0167-739X(03)00049-9]
• 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: Peter Benner , Volker Mehrmann , Hongguo Xu, A new method for computing the stable invariant subspace of a real Hamiltonian matrix, Journal of Computational and Applied Mathematics, v.86 n.1, p.17-43, Nov. 28, 1997 [doi>10.1016/S0377-0427(97)00146-5]
• 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: 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]
• 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: Ralph Byers, Hamiltonian and symplectic algorithms for the algebraic riccati equation, 1983
• 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: 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]
• 25: H. Van der Vorst , Paul Van Dooren, Parallel Algorithms for Numerical Linear Algebra, Elsevier Science Inc., New York, NY, 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: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 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: Tsung-Min Hwang , Wen-Wei Lin , Volker Mehrmann, Numerical Solution of Quadratic Eigenvalue Problems with Structure-Preserving Methods, SIAM Journal on Scientific Computing, v.24 n.4, p.1283-1302, 2002 [doi>10.1137/S106482750139220X]
• 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: Volker Mehrmann , David Watkins, Structure-Preserving Methods for Computing Eigenpairs of Large Sparse Skew-Hamiltonian/Hamiltonian Pencils, SIAM Journal on Scientific Computing, v.22 n.6, p.1905-1925, 2000 [doi>10.1137/S1064827500366434]
• 36: E. E. Osborne, On Pre-Conditioning of Matrices, Journal of the ACM (JACM), v.7 n.4, p.338-345, Oct. 1960 [doi>10.1145/321043.321048]
• 37: Parlett, B. N. and Reinsch, C. 1969. Balancing a matrix for calculation of eigenvalues and eigenvectors. Numerische Mathematik 13, 293--304.
• 38: 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]
• 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: Françoise Tisseur , Karl Meerbergen, The Quadratic Eigenvalue Problem, SIAM Review, v.43 n.2, p.235-286, 2001 [doi>10.1137/S0036144500381988]
• 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: J. H. Wilkinson , C. Rinsch , F. L. Bauer, Handbook for Automatic Computation: Linear Algebra (Grundlehren Der Mathematischen Wissenschaften, Vol 186), SpringerVerlag, 1986
• 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: Kemin Zhou , John C. Doyle , Keith Glover, Robust and optimal control, Prentice-Hall, Inc., Upper Saddle River, NJ, 1996

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

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

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Eigenvalues and eigenvectors (direct and iterative methods)
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Certification and testing; Documentation; Reliability and robustness; Algorithm design and analysis; Efficiency

General Terms:
Algorithms, Documentation, Performance

Keywords:
Algebraic Riccati equation, Hamiltonian matrix, eigenvalues, invariant subspaces, skew-Hamiltonian matrix, symplectic QR decomposition