HLIBpro  2.3.1
Block Cluster Tree

Given cluster trees for the index sets and , the product index set is to be partitioned. The trivial product of both cluster trees would yield a tree with 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.

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

which can usually be relaxed to

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

The boolean parameter defines the usage of or in the above admissibility condition and defaults to , 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 );

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:

The first parameter is again the 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.

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.: