Hierarchical matrix

Remarks

Each admissible block is stored as a product $X Y^T$ with $X$ of size $\abs{\tau} \times k$ and $Y$ of size $\abs{\sigma} \times k$. The blocks in $\mathcal{P}^{-}$ are stored in full; the partition is built so that they are small. In applications each index $i$ carries a point $x_i \in \R^d$, and $\Omega_\tau$ is the set of points of a cluster $\tau$. The standard admissibility condition is $\min(\operatorname{diam} \Omega_\tau, \operatorname{diam} \Omega_\sigma) \le \eta \operatorname{dist}(\Omega_\tau, \Omega_\sigma)$ for a fixed $\eta > 0$. With this condition, the matrices of asymptotically smooth kernels such as $1 / \abs{x - y}$ are well approximated by $\mathcal{H}$-matrices of small rank. Example: let $n = 2m$, split $I$ into halves $\tau_1$ and $\tau_2$, and call the two off-diagonal blocks admissible. A block diagonal matrix has zero off-diagonal blocks, of rank $0$, so it is an $\mathcal{H}$-matrix of every local rank $k$. Non-example: the exchange matrix, with ones on the antidiagonal, has off-diagonal blocks of rank $m$. So it is not an $\mathcal{H}$-matrix of local rank $k < m$ for this partition.