Parallel Black Box Domain Decomposition Based -LU Preconditioning

Lars Grasedyck, Ronald Kriemann, and Sabine Le Borne

Contact the author: Please use for correspondence this email.
Submission date: 08. Dec. 2005 (revised version: December 2005)
published as: Domain decomposition based H-LU preconditioning.
In: Numerische Mathematik, 112 (2009) 4, p. 565-600 
DOI number (of the published article): 10.1007/s00211-009-0218-6
published as: Parallel black box H-LU preconditioning for elliptic boundary value problems.
In: Computing and visualization in science, 11 (2008) 4-6, p. 273-291 
DOI number (of the published article): 10.1007/s00791-008-0098-9
Bibtex
MSC-Numbers: 65F05, 65F30, 65F50, 65N55
Keywords and phrases: hierarchical matrices, domain decomposition, nested dissection, lu, parallel

Abstract:
Hierarchical matrices provide a data-sparse way to approximate fully populated matrices. The two basic steps in the construction of an -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 -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 -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.