Overlapping Blocks by Growing a Partition with Applications to Preconditioning
David Fritzsche, Andreas Frommer, Stephen D. Shank, Daniel B. Szyld · SIAM Journal on Scientific Computing · 2013
Starting from a partitioning of an edge-weighted graph into subgraphs, we develop a method which enlarges the respective sets of vertices to produce a decomposition with overlapping subgraphs. The vertices to be added when growing a subset are chosen according to a criterion which measures the strength of connectivity with this subset. By using our method on the (directed) graph associated with a matrix, we obtain an overlapping decomposition of the set of variables which can be used for algebraic additive and multiplicative Schwarz preconditioners. We present a complexity analysis of this block-growing method, thus proving its computational efficiency. Numerical results for problems stemming from various application areas show that with these overlapping Schwarz preconditioners we usually substantially improve GMRES convergence as compared to preconditioners based on a nonoverlapping decomposition, or an overlapping decomposition based on level sets without other criteria, as well as incomplete LU.