A PhD thesis @ NALAG

TW 2010_05

Katrijn Frederix
Structured matrices and their applications
October 13, 2010

Advisor(s): Marc Van Barel

Abstract

In this thesis structured matrices are studied from a practical point of view. In general, algorithms which exploit the structure of matrices are designed, implemented and analyzed in the context of four problems coming from different fields. Each problem is translated to one of the basic linear algebra problems: solving a system of linear equations or an eigenvalue problem. Firstly, a dense linear system for rank structured matrices is solved using a direct method. This problem arises when solving a boundary integral equation. The related matrices could be approximated by matrices belonging to the class of rank structured matrices, namely matrices satisfying a certain rank structure R. To avoid the time-consuming evaluation of integrals, a novel construction for the unitary-weight representation is proposed, based on adaptive cross approximation.
Then two different problems are considered. First, the eigenvalues of a symmetric rationally generated Toeplitz matrix are computed. Secondly, the eigenvalues of a block companion matrix, which are the eigenvalues of the related matrix polynomial, are computed. Both kinds of matrices, the symmetric rationally generated Toeplitz matrices and the companion matrices, belong to the class of matrices satisfying a certain rank structure R. Therefore, the algorithms to compute the eigenvalues are both based on the Givens-weight representation which is a compact representation for a rank structured matrix.
Finally, an eigenvalue problem for structured matrices is studied. This problem appears in the subdivision of unlabeled data into meaningful groups by spectral clustering. The related similarity matrix is approximated in a way that captures the structure of the matrix, this plays a crucial role in spectral clustering. The approximation leads to an eigenvalue problem of smaller size. It is also possible to extend the method such that out-of-sample points are classified.
Numerical experiments are included for all the proposed methods.