Structured Eigenvalue Problems

The task of computing the eigenvalues or invariant subspaces of a matrix usually arises from applications in science or engineering only after a long process of simplifications, discretizations and linearizations. In most cases, the matrices obtained from such a process are highly structured. For example, matrix representations may contain redundancy, often in the form of sparsity, or inherit some of the physical properties from the original problem. This talk surveys some recent results on theory, algorithms, and software for such structured eigenvalue problems. In particular, we will describe a new approach to the structured perturbation analysis of invariant subspaces. This approach provides insight on the invariant subspace sensitivity for various structures including Hamiltonian, skew-Hamiltonian, product, Toeplitz, palindromic, and quaternion eigenvalue problems. Algorithms capable to preserve structures have the potential to compute eigenvalues and invariant subspaces in a more efficient and accurate manner than general-purpose algorithms. We will critically review the question for which structures the development of such algorithms is worthwhile and present new variants of algorithms for Hamiltonian and product eigenvalue problems. The talk will be concluded by HAPACK, a LAPACK-like software package for solving (skew-)Hamiltonian eigenvalue problems, and its application to pseudospectra computations. The work presented in this talk is joint work with Peter Benner, Ralph Byers, Heike Fassbender, Volker Mehrmann, and Emre Mengi.