# 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.