HLIBpro
3.0

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 Hcomputations 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.
The simplest form of admissibility assumes all offdiagonal blocks to be admissible. This equals the HODLR format (*H*ierachical *O*ffdiagonal *L*ow*R*rank).
This condition is implemented in TOffDiagAdmCond:
Assuming appropriate properties of the operator that should be represented by Hmatrices, 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( \operatorname{diam}(s), \operatorname{diam}(t) \right) \le \eta \cdot \operatorname{dist}(s,t) \]
which can usually be relaxed to
\[ \min\left( \operatorname{diam}(s), \operatorname{diam}(t) \right) \le \eta \cdot \operatorname{dist}(s,t) \]
The parameter \( \eta \) controls the ratio between the diameter and the distance, yielding a finer Hstructure when \( \eta \) tends to 0. By default \( \eta = 2 \) holds.
The implementation for the standard admissibility can be found in TStdAdmCond.
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:
For oscillating operators, e.g. Helmholtz or Maxwell, the rank of lowrank blocks in Hmatrices will grow linearlly with the wave number. For large wave numbers and large blocks, this will easilly lead to a very high rank and therefore significant memory usage and computation times.
Due to this property, standard Hmatrices are not capable of handling high frequency cases efficiently. However, in practise many problems may still be computed using Hmatrices. 𝖧𝖫𝖨𝖡𝗉𝗋𝗈 provides a modified admissibility condition (THiLoFreqGeomAdmCond), which limits the number of wave lengths per geometrical cluster and thereby also limits the rank:
Here, kappa
denotes the wave number and nwaves
defines the maximal number of wave lengths per cluster. In the low frequency case, the standard admissibility is applied, using the provided parameter eta
.
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 \( \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. Hmatrices 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.
The construction of the block cluster tree is generic, once the admissibility condition is defined and implemented in TBCBuilder:
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.: