MiS Preprint Repository

Delve into the future of research at MiS with our preprint repository. Our scientists are making groundbreaking discoveries and sharing their latest findings before they are published. Explore repository to stay up-to-date on the newest developments and breakthroughs.

MiS Preprint

Adaptive Geometrically Balanced Clustering of ${\cal H}$-Matrices

Lars Grasedyck, Wolfgang Hackbusch and Sabine Le Borne


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))$.

Apr 15, 2004
Apr 15, 2004
MSC Codes:
65F05, 65F30, 65N38, 65N50
hierarchical matrices, adaptive mesh refinement, boundary elements

Related publications

2004 Repository Open Access
Lars Grasedyck, Wolfgang Hackbusch and Sabine LeBorne

Adaptive geometrically balanced clustering of \(\mathscr {H}\)-matrices

In: Computing, 73 (2004) 1, pp. 1-23