| Home > Publications > PhD theses > Numerical Analysis and Applied Mathematics (TW) |
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.
