A PhD thesis @ NALAG

TW 2007_04

Steven Delvaux
Rank structured matrices

Advisor(s): Marc Van Barel

Abstract

Rank structured matrices form a subject of growing interest and importance in the numerical analysis and linear algebra literature. Recently it was shown how such matrices can be used e.g. for computing the eigenvalue decomposition of an arbitrary symmetric matrix using semiseparable matrices, for efficiently computing the zeros of a polynomial, and for approximating Toeplitz matrices. In addition, there is also the related class of hierarchically rank structured matrices, which has recently been used e.g. for approximating the discretized version of certain integral operators, and as an underlying framework for the Fast Multipole Method.

In this thesis we study rank structured matrices from both a theoretical and a practical point of view. The thesis consists of three parts.

In the first part we study the preservation of structure under several matrix operations, such as the QR-iteration algorithm, matrix inversion and Schur complementation. Each of these operations will lead us to the definition of an appropriate notion of rank structure. The rank structures may even contain what we call a shift correction term to the structure, i.e., a certain correction term which acts on the block diagonal elements of the structure.

In the second part we describe several practical algorithms for rank structured matrices whose structure consists of a set of contiguous low rank blocks situated in the lower left and upper right matrix corner. To this end, we first introduce the notion of unitary-weight and Givens-weight representations. Using these representations, we develop methods e.g. for solving a linear system of equations, and for computing all the eigenvalues (singular values) by means of the Hessenberg reduction algorithm (bidiagonal reduction algorithm). Numerical experiments demonstrate the stability and efficiency of the developed methods.

Finally, in the third part we study Fourier matrices and Kronecker products. We show that such matrices generally have a lot of low rank submatrices. We show how these low rank submatrices are related to the Fast Fourier Transform (FFT), and to an uncertainty principle for Fourier transforms over finite Abelian groups.