Iterative solution methods based on the Hierarchically Semi-Separable Representation

Abstract — In this paper, we study an important class of struc-tured matrices: ”Hierarchically Semi-Separable (HSS) ” matrices, for which an efficient hierarchical state based representation called Hierarchically Semi-Separable (HSS) representation can be used to utilize the data sparsity of the HSS matrices. A novel algorithm with O(n) complexity is proposed to construct sub-optimal HSS representations from sparse matrices. Subsequently, the limitation of the direct HSS solution method is discussed in this paper, and a general strategy to combine standard iterative solution methods with the HSS representation is presented. We also describe a number of preconditioner construction algorithms based on the HSS representation. Our numerical experiments in-dicate that these iterative solution methods have linear complexity in computation time. Index Terms — Iterative solution method, hierarchically semi-separable representation, preconditioner I