An overview of the use of rank structured matrices to solve eigenvalue problems

Marc Van Barel

When all eigenvalues (and eigenvectors) have to be computed for a given symmetric matrix, the classical QR-algorithm is used, i.e., the symmetric matrix is transformed into a symmetric tridiagonal one by orthogonal similarity transformations and then the QR-algorithm is applied to this tridiagonal matrix. Each step of the QR-algorithm applied to an n n tridiagonal matrix requires O(n) flops.

One could ask the question if there are other interesting structures that are maintained under the QR-algorithm and for which the QR-algorithm requires also only O(n) flops per iteration. In this talk, we will give an overview of the use of (symmetric) semiseparable matrices as an alternative to tridiagonal ones. A semiseparable matrix is a matrix where all submatrices that can be taken out of the lower triangular part (the main diagonal included) have maximum rank one. Using orthogonal similarity transformations any symmetric matrix can be reduced into a symmetric semiseparable one. The computational complexity of this reduction is the same as for the tridiagonal reduction. The implicit QR-algorithm on a semiseparable matrix can then be applied by a chasing technique. We will also have a look at divide-and-conquer techniques, Lanczos-type algorithms, ... .

If time permits, we will then focus our attention to more general rank structured matrices. We will illustrate the algorithms by showing several numerical examples.