Open Collections

Fast, Stable, Computation of the Eigenvalues of Unitary-plus-rank-one Matrices, including Companion Matrices

Banff International Research Station for Mathematical Innovation and Discovery

We consider upper Hessenberg unitary-plus-rank-one matrices, that is, matrices of the form $A = \tilde{U} + \tilde{x}\tilde{y}^{T}$, where $\tilde{U}$ is unitary, and $A$ is upper Hessenberg. This includes the class of Frobenius companion matrices, so methods for this type of matrix can be applied to the problem of finding the zeros of a polynomial. The unitary-plus-rank-one structure is preserved by any method that performs unitary similarity transformations, including Francis's implicitly-shifted $QR$ algorithm. We present a new implementation of Francis's algorithm that acts on a data structure that stores the matrix in $O(n)$ space and performs each iteration in $O(n)$ time. This is joint work with Jared Aurentz, Thomas Mach, and Raf Vandebril. Ours is not the first fast algorithm that has been proposed for this problem, but it is the first that has been shown to be backward stable, and it is faster than other fast algorithms that have been proposed previously.

Mathematics; Linear and multilinear algebra; matrix theory; Combinatorics

video/mp4

Author affiliation: Washington State University

2018-01-04

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/64255

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/