Table of Contents

Given cluster trees $ T(I), T(J) $ for the index sets $ I $ and $ J $ , the product index set $I \times J$ is to be partitioned. The trivial product of both cluster trees would yield a tree with $\mathcal{O}\left( \#I \cdot \# J \right)$ nodes, obviously exceeding the desired complexity. The restriction of the full product tree to those nodes, interesting for 𝓗-computations is performed by identifying admissibly blockes which are not refined, and for which the sub tree is eliminated from the product tree. For this identifcation the admissibility condition is used.

Admissibility Condition

Geometrical Case

Assuming appropriate properties of the operator that should be represented by 𝓗-matrices, the standard definition of admissibility uses diameters and distances between individual clusters. These terms have the standard definition in the geometrical case, e.g. the diameter of a cluster is the diameter of the bounding box or of the bounding sphere enclosing all indices and the distance is defined accordingly. Here, the standard admissibility condition is

$\max\left( \mathnormal{diam}(s), \mathnormal{diam}(t) \right) \le \eta \cdot \mathnormal{dist}(s,t)$

which can usually be relaxed to

$\min\left( \mathnormal{diam}(s), \mathnormal{diam}(t) \right) \le \eta \cdot \mathnormal{dist}(s,t)$

The parameter $\eta$ controls the ratio between the diameter and the distance, yielding a finer 𝓗-structure when $\eta$ tends to 0. By default $\eta = 2$ holds.

The implementation for the standard admissibility can be found in TStdAdmCond.

TStdAdmCond adm( 2.0, true );

The boolean parameter defines the usage of $\min$ or $\max$ in the above admissibility condition and defaults to $\min$ , e.g. the parameter is false.

If a periodicity was set for the coordinates, this must also be set for the admissibility. Otherwise, the distance between clusters is computed without this periodicity:

TPoint period( 1.0, 0.0 );

TStdAdmCond adm( period, 2.0 );

Algebraic Case

In the case of algebraic clustering, the above definitions of the admissibility condition can also be used, if corresponding definitions for the diameter and the distance of clusters are available. Since in 𝓗𝖫𝖨𝖡𝗉𝗋𝗈, algebraic clustering is based on graphs, both terms are defined in terms of path lengths. This leads to the implementation in TStdAlgAdmCond. It uses the sparse matrix for graph definition and furthermore, needs the mappings between internal and external ordering to correctly identify the indices:

TStdAlgAdmCond adm( 2.0, S, ct->perm_e2i(), ct->perm_i2e() );

The first parameter is again the $\eta$ from the definition of the admissibility condition.

Unfortunately, computing distances and diameters in graphs is costly. Since in algebraic clustering the correspondence between real spatial coordinates and the nodes in graphs is only an approximation, the admissibility condition may be further relaxed, leading to the weak algebraic admissibility. Here, a block cluster is admissible, if no edge connects the two corresponding sub graphs. 𝓗-matrices defined by this admissibility condition usually have similar approximation and complexity properties as in the standard admissibility case, but the test can be done much more efficiently. The implementation of this admissbility condition can be found in TWeakAlgAdmCond, which again needs the matrix and the mappings for the admissibility test.

TWeakAlgAdmCond adm( S, ct->perm_e2i(), ct->perm_i2e() );

Construction

The construction of the block cluster tree is generic, once the admissibility condition is defined and implemented in TBCBuilder:

TBCBuilder bct_builder;

autoptr< TBlockClusterTree > bct( bct_builder.build( ct.get(), ct.get(), & adm ) );

Objects of type TBlockClusterTree will not only store the actual tree but also the mappings between internal and external ordering supplied by the corresponding row and column cluster trees. In contrast to this a TBlockCluster object only represents the tree without any mappings. To access this tree from a TBlockClusterTree object, the root method is available, e.g.:

TBlockCluster * root = bct->root();