We have decided to discontinue the publication of preprints on our preprint server as of 1 March 2024. The publication culture within mathematics has changed so much due to the rise of repositories such as ArXiV (www.arxiv.org) that we are encouraging all institute members to make their preprints available there. An institute's repository in its previous form is, therefore, unnecessary. The preprints published to date will remain available here, but we will not add any new preprints here.
MiS Preprint
19/2004
Adaptive Geometrically Balanced Clustering of ${\cal H}$-Matrices
Lars Grasedyck, Wolfgang Hackbusch and Sabine Le Borne
Abstract
In previous papers, a class of (data-sparse) hierarchical ($\cal H$-) matrices is introduced that can be used to efficiently assemble and store stiffness matrices arising in boundary element applications. In this paper, we develop and analyse modifications in the construction of an $\cal H$-matrix that will allow an efficient application to problems involving adaptive mesh refinement. In particular, we present a new clustering algorithm such that, when an $\cal H$-matrix has to be updated due to some adaptive grid refinement, the majority of the previously assembled matrix entries can be kept whereas only a few new entries resulting from the refinement have to be computed. We provide an efficient implementation of the necessary updates and prove for the resulting $\cal H$-matrix that the storage requirements as well as the complexity of the matrix-vector multiplication are almost linear, i.e., ${\cal O}(n\log(n))$.
