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

ABSTRACT

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 Hamiltonian matrix to a square-reduced form transforms a Hamiltonian eigenvalue problem of order 2n to a Hessenberg eigenvalue problem of order n. The eigenvalues of the Hamiltonian matrix are the square roots of those of the Hessenberg matrix. Symplectic scaling and norm scaling are provided, which, in some cases, improve the accuracy of the computed eigenvalues. We demonstrate the performance of the subroutines for several examples and show how they can be used to solve some control-theoretic problems.

REFERENCES

• 1: AMMAR, G. AND MEHRMANN, V. 1991. On Hamiltonian and symplectic Hessenberg forms. Linear Alg. Appl. 149, 55-72.
• 2: AMMAR, G., BENNER, P., AND MEHRMANN, V. 1993. A multishift algorithm for the numerical solution of algebraic Riccati equations. Electr. Trans. Num. Anal. 1, 33-48.
• 3: 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
• 4: BENNER, P., BYERS, R., MEHRMANN, V., AND XU, H. 2000. Fortran 77 subroutines for computing the eigenvalues of Hamiltonian matrices II. In preparation.
• 5: BENNER, P., LAUB, A., AND MEHRMANN, V. 1995. A collection of benchmark examples for the numerical solution of algebraic Riccati equations I: Continuous-time case. Tech. Rep. SPC 95_22. Fakult t f r Mathematik, TU Chemnitz-Zwickau, Chemnitz, Germany. Available via http://www.tu-chemnitz.de/sfb393/spc95pr.html.
• 6: BENNER, P., MEHRMANN, V., AND XU, H. 1998. A numerically stable, structure preserving method for computing the eigenvalues of real Hamiltonian or symplectic pencils. Numer. Math. 78, 329-358.
• 7: S. Boyd , V. Balakrishnan, A regularity result for the singular values of a transfer matrix and a quadratically convergent algorithm for computing its L∞ -norm, Systems & Control Letters, v.15 n.1, p.1-7, Jul. 1990 [doi>10.1016/0167-6911(90)90037-U]
• 8: BOYD, S., BALAKRISHNAN, V., AND KABAMBA, P. 1989. A bisection method for computing the Y~- norm of a transfer matrix and related problems. Math. Control Syst. 2, 207-219.
• 9: N. A. Bruinsma , M. Steinbuch, A fast algorithm to computer the H∞ -norm of a transfer function matrix, Systems & Control Letters, v.14 n.4, p.287-293, April 1990 [doi>10.1016/0167-6911(90)90049-Z]
• 10: BUNCH, J. 1987. The weak and strong stability of algorithms in numerical algebra. Linear Alg. Appl. 88, 49-66.
• 11: BUNSE-GERSTNER, A. AND MEHRMANN, V. 1986. A symplectic QR-like algorithm for the solution of the real algebraic Riccati equation. IEEE Trans. Automat. Contr. AC-31, 12 (Dec.), 1104-1113.
• 12: BUNSE-GERSTNER, A., MEHRMANN, V., AND WATKINS, D. 1989. An SR algorithm for Hamiltonian matrices based on Gaussian elimination. Meth. Oper. Res. 58, 339-358.
• 13: Ralph Byers, Hamiltonian and symplectic algorithms for the algebraic riccati equation, 1983
• 14: Ralph Byers, A Hamiltonian QR algorithm, SIAM Journal on Scientific and Statistical Computing, v.7 n.1, p.212-229, Jan. 1986 [doi>10.1137/0907015]
• 15: BYERS, R. 1988. A bisection method for measuring the distance of a stable to unstable matrices. SIAM J. Sci. Stat. Comput. 9, 5, 875-881.
• 16: DAVISON, E. AND GESING, W. 1978. The systematic design of control systems for the multivariable servomechanism problem. In Alternatives for Linear Multivariable Control, M. Sain, J. Peczkowsky, and J. Melsa, Eds. Alternatives for Linear Multivariable Control, Chicago, IL.
• 17: 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]
• 18: Jack J. Dongarra , Jeremy Du Croz , Sven Hammarling , Richard J. Hanson, An extended set of FORTRAN basic linear algebra subprograms, ACM Transactions on Mathematical Software (TOMS), v.14 n.1, p.1-17, March 1988 [doi>10.1145/42288.42291]
• 19: DOYLE, J., GLOVER, K., KHARGONEKAR, P. P., AND FRANCIS, B.A. 1989. State-space solutions to standard H2 and Ha control problems. IEEE Trans. Automat. Contr. 34, 8, 831-847.
• 20: FRANCIS, B. 1987. A course in Y~ control theory. Springer Lecture Notes in Computer Science, vol. 88. Springer-Verlag, Vienna, Austria.
• 21: Judith D. Gardiner, A Stabilized Matrix Sign Function Algorithm for Solving Algebraic Riccati Equations, SIAM Journal on Scientific Computing, v.18 n.5, p.1393-1411, Sept. 1997 [doi>10.1137/S1064827593259078]
• 22: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 23: C. Kenney , A. J. Laub , M. Wette, A stability-enhancing scaling procedure for Schur-Riccati solvers, Systems & Control Letters, v.12 n.3, p.241-250, Apr. 1989 [doi>10.1016/0167-6911(89)90056-X]
• 24: LANCASTER, P. AND RODMAN, L. 1995. The Algebraic Riccati Equation. Oxford University Press, Oxford, UK.
• 25: LAUB, A. 1979. A Schur method for solving algebraic Riccati equations. IEEE Trans. Automat. Contr. AC-24, 6 (Dec.), 913-921.
• 26: C. L. Lawson , R. J. Hanson , D. R. Kincaid , F. T. Krogh, Basic Linear Algebra Subprograms for Fortran Usage, ACM Transactions on Mathematical Software (TOMS), v.5 n.3, p.308-323, Sept. 1979 [doi>10.1145/355841.355847]
• 27: PAIGE, C. AND VAN LOAN, C. 1976. A Schur decomposition for Hamiltonian matrices. Linear Alg. Appl. 14, 11-32.
• 28: PANDEY, P. 1993. On scaling an algebraic Ricatti equation. In Proceedings of the American Control Conference (San Francisco, CA, June), 1583-1587.
• 29: Beresford N. Parlett , Jian Le, Forward instability of tridiagonal QR, SIAM Journal on Matrix Analysis and Applications, v.14 n.1, p.279-316, Jan. 1993 [doi>10.1137/0614022]
• 30: PARLETT, B. AND REINSCH, C. 1969. Balancing a matrix for calculation of eigenvalues and eigenvectors. Numer. Math. 13, 296-304.
• 31: R. V. Patel , Z. Lin , P. Misra, Computation of Stable Invariant Subspaces of Hamiltonian Matrices, SIAM Journal on Matrix Analysis and Applications, v.15 n.1, p.284-298, Jan. 1994 [doi>10.1137/S0895479889171352]
• 32: P. Petkov , N. D. Christov , M. M. Konstantinov, On the numerical properties of the schur approach for solving the matrix Riccati equation, Systems & Control Letters, v.9 n.3, p.197-201, September 1, 1987 [doi>10.1016/0167-6911(87)90040-5]
• 33: RAINES, A. AND WATKINS, D. 1994. A class of Hamiltonian-symplectic methods for solving the algebraic Riccati equation. Linear Alg. Appl. 205/206, 1045-1060.
• 34: SIMA, V. 1992. Algorithm GRICSR: Solving continuous-time algebraic Ricatti equations using Gaussian symplectic transformations. Stud. Inf. Control 1, 1, 237-254.
• 35: SMITH, B. T., BOYLE, J. M., DONGARRA, J. J., GARBOW, B. S., IKEBE, Y., KLEMA, V. C., AND MOLER, C.B. 1976. Matrix Eigensystem Routines: EISPACK Guide. 2nd Springer Lecture Notes in Computer Science, vol. 6. Springer-Verlag, New York, NY.
• 36: SREEDHAR, J., VAN DOOREN, P., AND TITS, A. 1995a. A fast algorithm to compute the real structured stability radius. In Stability Theory. Proceedings of the Hurwitz Centenary Conference (Ticino, May 21-26), Birkh user, Basel, 219-230. Int. Ser. Numer. Math. 121.
• 37: SREEDHAR, J., VAN DOOREN, P., AND TITS, A. 1995b. A level-set idea to compute the real Hurwitz-stability radius. In Proceedings of the 34th IEEE Conference on Decision and Control (New Orleans, LA, Dec. 13-15), IEEE Press, Piscataway, NJ, WA05.
• 38: VAN LOAN, C. 1984. A symplectic method for approximating all the eigenvalues of a Hamiltonian matrix. Linear Alg. Appl. 61,233-251.
• 39: J. H. Wilkinson, The algebraic eigenvalue problem, Oxford University Press, Inc., New York, NY, 1988
• 40: Xu, H. 1993. Solving algebraic Riccati equations via Skew-Hamiltonian matrices. Ph.D. Dissertation. Institute of Mathematics, Fudan University, Shanghai, People's Republic of China.
• 41: Xu, H. AND LU, L. 1995. Properties of a quadratic matrix equation and the solution of the continuous-time algebraic Riccati equation. Linear Alg. Appl. 222, 127-145.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Eigenvalues and eigenvectors (direct and iterative methods)

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

          Nouns: FORTRAN 77

  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.4 MATHEMATICAL SOFTWARE
      Subjects: Documentation; Efficiency; Algorithm design and analysis; Reliability and robustness; Certification and testing

General Terms:
Algorithms, Documentation, Performance

Keywords:
(square-reduced), Hamiltonian matrix, algebraic Riccati equation, eigenvalues, skew-Hamiltonian matrix