Premium
Effects of problem decomposition (partitioning) on the rate of convergence of parallel numerical algorithms
Author(s) -
Cullum Jane K.,
Johnson Keith,
Tůma Miroslav
Publication year - 2003
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/nla.323
Subject(s) - robustness (evolution) , rate of convergence , algorithm , mathematics , partition (number theory) , computation , constructive , convergence (economics) , mathematical optimization , computer science , combinatorics , key (lock) , biochemistry , chemistry , computer security , process (computing) , economics , gene , economic growth , operating system
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. Copyright © 2003 John Wiley & Sons, Ltd.