Hierarchically semi-separable representation and its applications

Hierarchically semi-separable representation and its applications

Sheng, Z.

Dewilde, P. (mentor)
van der Veen, A.J. (mentor)
van der Meijs, N. (mentor)
Remis, R.F. (mentor)

Electrical Engineering, Mathematics and Computer Science

2006-06-01

In this thesis, we study a important class of structured matrices: "Hierarchically Semi-Separable" matrices, for which an efficient hierarchically state based representation called Hierarchically Semi- Separable (HSS) representation can be used to represent it with a small amount of parameters that are linear in the dimension of the matrix. Under the framework of this HSS representation, efficient matrix transformation algorithms that are linear in the number of equations are given. In particular, a system Ax = b can be solved with linear complexity. Also, LU and URV factorization can be efficiently executed. There is a close connection between HSS matrices and classical Semi Separable matrices (sometimes called Sequentially Semi Separable matrices or SSS matrices or equivalently, time-varying systems), and a number of results of SSS theory can be translated to parallel results in the HSS theory (neither class contains the other however). We also discuss the limitation of the direct HSS algorithms, for which iterative solution algorithms based on HSS representation and its basic algorithms should come to rescue. A number of preconditioner construction algorithms based on HSS representation have been proposed.

hierarchically semi-separable matrix
linear solver
preconditioner
lu
urv factorization

http://resolver.tudelft.nl/uuid:e7a452de-6859-42bc-97b6-3eb28815dc8b

TU Delft, Electrical Engineering, Mathematics and Computer Science, Information and Communication Technology (ICT)

Student theses

master thesis

(c) 2006 Z. Sheng