Construction and complexity of hierarchical matrices

In previous papers a class of ℋ-matrices was introduced which are data-sparse and allow an approximate matrix arithmetic of nearly optimal complexity. The complexity analysis for the (approximate) matrix arithmetics in the class of ℋ-matrices is based on two criteria, the sparsity and the idempotency. We describe a general strategy for the construction of the ℋ-matrices where the two criteria are fulfilled.