Clustering¶
HLR implements different clustering methods, which permits direct comparison between the different arithmetic implementations. By default all clustering is cardinality balanced. If not defined otherwise, e.g., HODLR, standard admissibility is used.
TLR/BLR¶
Tile Low-Rank (TLR) or block low-rank (BLR) clustering directly decomposes a given set of coordinates into clusters without any hierarchy. The matrix partitioning then consists of a simple \(p \times p\) block structure of either dense or low-rank blocks, thereby drastically simplifying algorithm design.
However, the runtime and storage complexity is increased to \(\mathcal{O}(n^3)\) and \(\mathcal{O}(n^2)\), respectively.
MBLR¶
MBLR extends TLR by using a fixed, predefined number of hierarchy levels with an even reduction of the block size per level. With a growing number of levels, MBLR converges to the standard H clustering.
TileH¶
TileH (also called Lattice-H in the literature) splits the top-layer of the cluster tree into \(p\) sub blocks resulting in a \(p \times p\) block layout. However, in contrast to TLR H-matrices are used for the corresponding sub blocks in the matrix. As with TLR, simple algorithms may be used on the first level of the matrix hierarchy, e.g., for distributed memory versions of the arithmetic, while maintaining log-linear complexity for the remaining H-matrix. This is also identical to various domain-decomposition approaches using H-matrices.
HODLR¶
Hierarchical Off-Diagonal Low-Rank (HODLR) clustering uses standard cluster tree construction but simplifies admissibility such that all off-diagonal matrix blocks are considered admissible. The resulting H-matrix has a \(2 \times 2\) block structure with upper right and lower left low-rank blocks.
H-arithmetic again is significantly simpler to implement. However, the rank of the low-rank blocks is typically dependent on the problem dimension and may be very large.
H¶
This is the standard, general H-matrix format with binary space partitioning and standard admissibility.
