A PhD thesis @ NALAG

TW 2004_03

Raf Vandebril
Semiseparable matrices and the symmetric eigenvalue problem

Advisor(s): Marc Van Barel

Abstract

In this thesis one of the basic linear algebra problems is considered, namely the symmetric eigenvalue problem. More precisely we translate the traditional method, based on tridiagonal matrices towards a tool based on semiseparable matrices. Three important parts are considered.

Firstly, the connection between the class of semiseparable matrices and tridiagonal matrices is thoroughly investigated. We define semiseparable matrices, such that the invertible ones have as inverse a tridiagonal matrix, and vice versa. It is shown that the symmetric semiseparable matrices can be represented by a Givens-vector representation having 2n-1 parameters. Moreover, we show that this representation has nice numerical properties when solving eigenvalue problems.

In the second part of the algorithm, a method is proposed, for reducing, via orthogonal similarity transformations a matrix into a similar semiseparable one. The constructed method inherits some convergence properties, such as subspace iteration, and a type of Lanczos-convergence, which are fully investigated.

In the final part of the thesis, a detailed investigation is made of the QR-factorization of semiseparable matrices, unreduced semiseparable matrices, and an implicit Q-theorem for semiseparable matrices; leading to an implicit QR-algorithm for semiseparable matrices.

The combination of the results of Part 2 and 3 leads to a solver for the symmetric eigenvalue problem. Even more, an adaptation of the results presented in these parts is included, such that also the unsymmetric eigenvalue problem, and the singular value problem, can now be solved via semiseparable matrices.

Numerical experiments are included, and the corresponding software is made available.