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
< Back