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.