Arithmetic

The power of hierarchical matrices is not obly in the data-sparse representation of dense data but furthermore also in the availability of full matrix arithmetic, e.g., matrix-vector multiplication, matrix addition and multiplication, matrix inversion and factorization. All these operations are typically performed with log-linear runtime and memory complexity, enabling efficient usage of different algorithms for a wide range of applications.

Arithmetic for hierarchical matrices can be implemented in different forms, while the main difference is the way in which updates are applied to low-rank blocks and how those are represented.

Furthermore, parallelization often requires special handling, which leads to modified formulations of the arithmetic.

Update Handling

Immediate Updates

Accumulated Updates

Lazy Updates

(Semi-) Uniform H-Matrices

Parallelization

Recursive Formulation

Task-Graphs