﻿ 数学与系统科学研究院

Max-Planck-Institut, Leipzig, Germany

Abstract: Hierarchical matrices ($\mathcal{H}$-matrices) are a tool for approximating dense matrices associated with elliptic pseudo-differential operators. In particular, they are suited for the discretisation of integral operators as they appear, e.g., in the boundary element method. But $\mathcal{H}$-matrices can also be used to represent the (fully populated) inverse of a finite-element stiffness matrix.

The storage of an $\mathcal{H}$-matrix of size $n\times n$ amounts to $O(n\log^{\alpha}n),$ where $\alpha$ is a small number depending an the variant of the $\mathcal{H}$-matrix (there are even variants with $\alpha=0).$

The important feature of $\mathcal{H}$-matrices is the fact that not only the matrix-vector multiplication but also all matrix operations (matrix-matrix addition, matrix-matrix multiplication and inversion) can be performed approximately. Again the operation cost is linear in $n$ up to logarithmic factors.

The construction of an $\mathcal{H}$-matrix is based on a block-cluster tree, which is close to the cluster tree using in the panel clustering method for the fast matrix-vector multiplication in boundary element methods. Given the set of degrees of freedom together with geometric information (e.g., support of the basis functions) a block partitioning can be computed. Each block is filled with a low-rank matrix. The rank is a parameter which can be used to obtain the desired accuracy (difference of the true matrix and the $\mathcal{H}$-matrix). Since the details of the discretisation do not enter the algorithm, the construction is black-box like.

In the case of boundary element methods, one uses to $\mathcal{H}$-matrices to avoid the dense system matrix, which requires that the approximation is sufficiently well. In the case of finite-element applications, at least a preconditioner (e.g., of a Schur complement problem) can be constructed by means of a rough $\mathcal{H}$-matrix approximation.

However, there are further applications where the standard reduction to the matrix-times-vector operation is not sufficient. Examples are matrix functions (e.g., the exponential of a matrix) and the solution of matrix Riccati equation, which can be achieved by means of $\mathcal{H}$-matrices.