Effects of problem decomposition (partitioning) on the rate of convergence of parallel numerical algorithms

摘要

We focus on the interplay between the choice of partition (problem decomposition) and the corresponding rate of convergence of parallel numerical algorithms. Using a specific algorithm, for which the numerics depend upon the partition, we demonstrate that the rate of convergence can depend strongly on the choice of the partition. This dependence is shown to be a function of the algorithm and of the choice of problem. Information gleaned from tests using various 2-way partitions leads to new partitions for which some degree of convergence robustness is exhibited. The incorporation of a known correction for approximate Schur complements into the original algorithm yields a modified parallel algorithm which numerical experiments indicate achieves robust convergence behaviour with respect to the choice of partition. We conclude that tests of a parallel algorithm which vary the method of partitioning can provide constructive information regarding the robustness of the algorithm and guidance for modifying the algorithm or the choice of partitioning algorithm to make the overall computations more robust.