Clustering describes the reorganisation of index sets, and thereby of the unknowns of the problem to solve, to make H-matrix approximation possible. It allows the identification of admissible and therefore, approximable blocks in the matrix. Clustering itself is split into the computation of the cluster tree, i.e. the clustering of an index set $I$ , and the computation of the block cluster tree, i.e. the clustering of a product index set $I \times I$ .

An important property of clustering is the permutation of the indices as the ordering used within an 𝓗-matrix will usually be different from the ordering used by the application, e.g. where it is defined by grid points or basis functions. In 𝓗𝖫𝖨𝖡𝗉𝗋𝗈 the original ordering of the indices is refered to as external ordering, whereas the ordering inside a cluster tree or an 𝓗-matrix is refered to as internal ordering. Mappings to convert between both orderings are computed during clustering in the form of permutations, either named i2e to map from internal to external ordering or e2i for external to internal mapping.

Table of Contents