数学与系统科学研究院
计算数学所学术报告
报告人： Wolfgang Hackbusch
Max-Planck-Institut, Leipzig, Germany
报告题目 Hierarchical matrices
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.
报告时间：2004年7月28日 下午4：15
报告地点：科技综合楼三层报告厅