Algorithm 800

Algorithm 800. Fortran 77 subroutines for computing the eigenvalues of Hamiltonian matrices. I: The square-reduced method. The authors describe a set of LAPACK-based Fortran 77 subroutines for reducing a Hamiltonian matrix to square-reduced form using orthogonal symplectic transformations and for approximating all of its eigenvalues using an implicit version of Van Loan’s method. This approach requires less than half as many FLOPS as are needed by the general QR algorithm. Routines are provided for computing the square-reduced form, computing the eigenvalues using the output from the first routine, computing the eigenvalues (this routine is easy to use), and symplectic and norm scaling. There is a comprehensive discussion of the numerical tests used, which include several applications in control theory. Tests on randomly generated matrices confirm that the reduction in FLOPS is reflected in a similar reduction in execution times compared to the general QR routine, DGEEVX, from the LAPACK library. The authors’ software also preserves the plus-minus eigenvalue pairs of the Hamiltonian, which are destroyed by rounding errors using DGEEVX. The eigenvalues of larger magnitude are computed to an accuracy in line with their condition numbers; very small eigenvalues may be perturbed by up to the square root of the unit rounding error. Such a loss of accuracy may sometimes (but not always) be avoided by scaling. Of the three scaling strategies mentioned (norm, symplectic, and Hessenberg), norm scaling was found to be the least effective in practice. (review ACM) (Source:

This software is also peer reviewed by journal TOMS.