Jared Aurentz

(Department of Mathematics, ICMAT Madrid)

Core-chasing algorithms for the eigenvalue problem

Date Friday, October 7, 2016

If $A$ is an $n times n$ upper Hessenberg matrix, the decomposition $A = QR$ is particularly simple: the unitary matrix $Q$ is a product of a descending sequence of $n-1$ core transformations (e.g. Givens rotations) $Q_1cdots Q_{n-1}$. Thus the space required to store the decomposed form is not appreciably greater than that required to store $A$ in the conventional way. For certain classes of structured eigenvalue problems we (and others before us) have found it useful to store A in this QR-decomposed form and operate on the factors. We mention in particular the unitary-plus-rank-one case, which includes companion matrices, and the even simpler unitary case.

In this talk we will argue that even if $A$ has no special structure, it is still worthwhile to do the QR decomposition and work with the factored form. If we apply Francis's implicitly-shifted QR algorithm to the matrix in this form, it becomes a process of chasing an unwanted core transformation through the matrix until it is eliminated at the bottom. Thus it is a core-chasing algorithm instead of a bulge-chasing algorithm.

We will demonstrate that algorithms of this type are backward stable, paying special attention to the unitary-plus-rank-one (companion) case.