Balancing a matrix by a simple and accurate similarity transformation can improve
the speed and accuracy of numerical methods for computing eigenvalues. We describe
balancing strategies for a large and sparse Hamiltonian matrix H. It is first shown how
to permute H to irreducible form while retaining its structure. This form can be used to
decompose the Hamiltonian eigenproblem into smaller-sized problems. Next, we discuss
the computation of a symplectic scaling matrix D so that the norm of D 1 HD is reduced.
The considered scaling algorithm is solely based on matrix-vector products and thus particularly
suitable if the elements of H are not explicitly given. The merits of balancing
for eigenvalue computations are illustrated by several practically relevant examples.
The periodic QR algorithm is a strongly backward stable method for computing the
eigenvalues of products of matrices, or equivalently for computing the eigenvalues of
block cyclic matrices. The main purpose of this paper is to show that this algorithm
is numerically equivalent to the standard QR algorithm. It will be demonstrated
how this connection may be used to develop a better understanding of the periodic
QR algorithm.
Two algorithms for the solution of discrete-time periodic Lyapunov
equations are presented. The first one is a variant of the
squared Smith iteration, which is solely based on matrix multiplications
and thus attractive to parallel computing environments.
The second algorithm is based on Krylov subspaces and
employs a recently developed variant of the block Arnoldi algorithm.
It is particularly suited for periodic Lyapunov equations
with large and sparse coefficient matrices. We also demonstrate
how these methods can be applied to balanced truncation model
reduction of periodic discrete-time systems and the solution of
periodic Riccati equations.
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.
Stewart's recently introduced Krylov-Schur algorithm
is a modification of the implicitly restarted Arnoldi algorithm which
employs reordered Schur decompositions to perform restarts and de-
ations in a numerically reliable manner. This paper describes a variant
of the Krylov-Schur algorithm suitable for addressing eigenvalue
problems associated with products of large and sparse matrices. It
performs restarts and de
ations via reordered periodic Schur decompositions
and, by taking the product structure into account, it is
capable to achieve qualitatively better approximations to the eigenvalues
of small magnitude.
The role of larger bulges in the QR algorithm is controversial. Large bulges are infamous
for having a strong, negative influence on the convergence of the implicit shifted QR algorithm.
This paper provides a new explanation of this shift blurring effect by connecting the computation of
the first column of the shift polynomial to the notoriously ill-conditioned pole placement problem.
To avoid shift blurring, modern variants of the QR algorithm employ chains of tightly coupled tiny
bulges instead of one large bulge. It turns out that larger bulges still play a positive role in these
variants; a slight increase of the bulge sizes often results in considerable performance improvements.
We investigate the condition number for a complex eigenvalue of a real matrix under
real perturbations. Based on an explicit formula, it is shown that this number is never
smaller than 1/
p
2 times the corresponding condition number with respect to complex
perturbations. This result can be generalized to the condition number of an arbitrary
complex-valued function under real perturbations. This extends to related condition
numbers.
Stewart's recently introduced Krylov-Schur algorithm
is a modification of the implicitly restarted Arnoldi algorithm which
employs reordered Schur decompositions to perform restarts and de-
ations in a numerically reliable manner. This paper describes a variant
of the Krylov-Schur algorithm suitable for addressing eigenvalue
problems associated with products of large and sparse matrices. It
performs restarts and de
ations via reordered periodic Schur decompositions
and, by taking the product structure into account, it is
capable to achieve qualitatively better approximations to the eigenvalues
of small magnitude.
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.