Hierarchically semi-separable representation and its applications

Abstract

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.