Volume 33, pp. 163-188, 2008-2009.

Transforming a hierarchical into a unitary-weight representation

Steven Delvaux, Katrijn Frederix, and Marc Van Barel

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 ${\mathcal{H}}^2$-matrices. We describe a fast ($O(r^{3}n\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.

Full Text (PDF) [296 KB], BibTeX

Key words

hierarchically semiseparable (HSS) matrix, ${\mathcal{H}}^2$-matrix, low rank submatrix, tree, QR factorization, unitary-weight representation

AMS subject classifications

65F30, 15A03