Introduction into hierarchical matrices

Abstract: 

The technique of hierarchical matrices tries to approximate fully populated large-scale matrices in a representation only requiring a storage of O(n log(n)). Of similar importance is the fact the all matrix operations (including inversion and LU decomposition) can be performed with similar cost. In particular, this method applies to matrices originating from elliptic problems. The full matrices of boundary integral equations can be treated in this way. The standard finite element matrix is sparse, but its inverse and its LU factors are not. However, computing these matrices in the hierarchical format is of almost linear cost. Using the (approximate) LU factors, one is able to construct fast iterative methods in a blackbox fashion. Having at hand all matrix operations, we can compute matrix functions and solve matrix equations.

Literature

W. Hackbusch: Hierarchical Matrices - Algorithms and Analysis. SSCM 49, Springer 2015