Parallel black box ℋ-LU preconditioning for elliptic boundary value problems
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 the context of finite element discretisations of elliptic boundary value problems, ℋ-matrices can be used for the construction of preconditioners such as approximate ℋ-LU factors. In this paper, we develop a new black box approach to construct the necessary partition. This new approach is based on the matrix graph of the sparse stiffness matrix and no longer requires geometric data associated with the indices like the standard clustering algorithms. The black box clustering and a subsequent ℋ-LU factorisation have been implemented in parallel, and we provide numerical results in which the resulting black box ℋ-LU factorisation is used as a preconditioner in the iterative solution of the discrete (three-dimensional) convection-diffusion equation.
Black box clustering