A Nested-Dissection Based Schur Complement Low Rank Correction Preconditioner
Motivation: Large systems of equations with weakly bounded equations can be solved iteratively by so-called Krylov space methods, whereby the convergence properties depend on the construction of a suitable preconditioner. The Power Schur Complement Low-Rank Correction proposed by Zheng, Xi, Saad [1].
(PSLR) preconditioner uses as an approach an area decomposition into several disjoint subareas and an inner boundary, in which boundary nodes are connected with nodes from only one subarea. It will be investigated how an alternative nested dissection decomposition affects the preconditioner.
Methods: The area decomposition into several disjoint subareas is to be replaced by a nested dissection approach, i.e. a decomposition into only two disjoint subareas with the smallest possible inner boundary and subsequent recursive application of the decomposition within the subareas.
Such decompositions are typically determined via the matrix graph. The underlying structure of the preconditioner, based on a power series expansion and low-rank correction, is to be retained and formulated recursively. The resulting algorithm uses various methods from numerical linear algebra. Both approaches will be compared by extensive numerical tests.
Project goals and work packages:
– Working through the article [1]
– Implementation (C/C++) of the area decomposition into several disjoint subareas with boundary (as in [1]) as well as the nested dissection decomposition (if necessary using the METIS package).
– Implementation of the preconditioner from [1] and adaptation to the nested dissection decomposition (recursion)
– Extensive tests and documentation of numerical results with regard to convergence rates, parallelisability, computational and memory requirements; application problems here are elliptic partial differential equations in two and three spatial dimensions (implementations of the test problems are already available).
