Comparison of LR-Approximation and H-arithmetic

In this program, different H-arithmetic and low-rank approximation techniques are compared for a given application, clustering and H-function.

Currently, H-matrix multiplication (approx-mm) and H-LU factorization (approx-lu) are implemented.


HLR implements the following H-arithmetic versions:


after computation of an update this is immediately applied to the destination blocks, with a subsequent low-rank truncation in case of low-rank blocks.


accumulate all update per level in a low-rank matrix from root to leaves, thereby shifting down accumulated updates to sub-blocks. Apply all accumulated updates to leaf block in last step.


for each leaf block collect all updates as a list of corresponding products (or matrices) and apply the sum of all updates simultaneously in final step.

See also Arithmetic for more information.

Low-Rank Approximation

The following low-rank approximation techniques are available in HLR and used in the comparison:

  • SVD: Singular Value Decomposition

  • RRQR: Rank Revealing QR

  • RandLR/SVD: Randomized LR and Randomized SVD

  • ACA: Adaptive Cross Approximation

  • Lanczos: Lánczos Bidiagonalization

See also Approximation for more information.


Below you can choose between different settings for H-function, application, etc. and see precomputed results. The figure shows the relative runtime, error and memory consumption of the different H-arithmetic and low-rank approximation techniques with the baseline defined by the classical H-arithmetic (immediate updates with low-rank SVD).

If any arithmetic or approximation algorithm is missing in the comparison, this is either due to an error, e.g., failed to converge, or because runtime/approximation was beyond any practical value.

Please note that, depending on the values, the x-axis uses logarithmic scaling.

1e-4 8k


All computations were performed on an Intel Xeon E5-2698 v4. Only a single core was used, e.g., sequential computation, to focus on general arithmetic and approximation properties.