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

Parallel Black Box Domain Decomposition Based ${\cal H}$-LU Preconditioning

Lars Grasedyck, Ronald Kriemann and Sabine Le Borne


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.

Dec 8, 2005
Dec 8, 2005
MSC Codes:
65F05, 65F30, 65F50, 65N55
hierarchical matrices, domain decomposition, nested dissection, lu, parallel

Related publications

2009 Journal Open Access
Lars Grasedyck, Ronald Kriemann and Sabine LeBorne

Domain decomposition based \(\mathscr {H}\)-LU preconditioning

In: Numerische Mathematik, 112 (2009) 4, pp. 565-600