Electronic Transactions on Numerical Analysis.

Abstract. In this paper, we consider a class of hierarchically rank structured matrices that includes some of the hierarchical matrices occurring in the literature, such as hierarchically semiseparable (HSS) and certain H2-matrices. We describe a fast (O(r3n log(n))) and stable algorithm to transform this hierarchical representation into a so-called unitary-weight representation, as introduced in an earlier work of the authors. This reduction allows the use of fast and stable unitary-weight routines (or by the same means, fast and stable routines for sequentially semiseparable (SSS) and quasiseparable representations used by other authors in the literature), leading, e.g, to direct methods for linear system solution and for the computation of all the eigenvalues of the given hierarchically rank structured matrix. Key words. hierarchically semiseparable (HSS) matrix, H2-matrix, low rank submatrix, tree, QR factorization, unitary-weight representatio