Transforming a hierarchical into a unitary-weight representation

In this paper we consider a class of hierarchically rank structured matrices, including 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.nrpages: 27status: publishe