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
115/2005
Parallel Black Box Domain Decomposition Based ${\cal H}$-LU Preconditioning
Lars Grasedyck, Ronald Kriemann and Sabine Le Borne
Abstract
Hierarchical matrices provide a data-sparse way to approximate fully populated matrices. The two basic steps in the construction of an ${\cal H}$-matrix are (a) the hierarchical construction of a matrix block partition, and (b) the blockwise approximation of matrix data by low rank matrices. In this paper, we develop a new approach to construct the necessary partition. This new approach is based on a domain decomposition technique and yields a block structure in which large subblocks of the finite element stiffness matrix are zero and remain zero in a subsequent LU factorization, thus leading to, rigorously proven and numerically verified, improved storage and computational complexity requirements compared to ${\cal H}$-matrices constructed by a standard geometric bisection process. Furthermore, we introduce a black box clustering technique which no longer requires geometric grid information. The new algorithms have been implemented in parallel, and we provide numerical results in which an ${\cal H}$-LU factorization based on black box domain decomposition clustering is used as a preconditioner in the iterative solution of the discrete (three-dimensional) convection-diffusion equation.
