The aim of this lecture is to give an introduction to the matrix compression format of hierarchical matrices, to provide a mathematical analysis for which problem classes it can suitably be applied, and introduce the essential algorithms as well as analyze their computational cost.
Other compression techniques such as H^2-matrices are introduced as well.
Elementary operations with N × N-matrices such as addition and matrix-vector-multiplication (MVM) usually need at least O(N^2) arithmetic operations, which leads to an unsurmountable computational effort for large scale problems.
In order to (approximatively) reduce the complexity of storage and MVM for an important class of matrices (e.g. obtained from discretizations of integral equations) to linear complexity O(N), the fast multipole method (FMM) was developed in 1987, and was voted to one of the top 10 algorithms of the 20th century.
An algebraic generalization of the FMM was developed in 1999 with the matrix compression format of hierarchical matrices (H-matrices). In comparison to other compression techniques (like the FMM) H-matrices stand out with the fact that additionally to storage and MVM they provide (approximative) arithmetic operations like addition, multiplication
and inversion in (logarithmic) linear complexity O(N log N).
In this lecture, the format of hierarchical matrices are introduced and mathematically and algorithmically analyzed. Finally, other compression techniques such as H^2-matrices (linear complexity O(N)) are introduced.
