Effects of Problem Decomposition (Partitioning) on the Rate of Convergence of Parallel Numerical Algorithms

0092642 - ÚI 2008 RIV GB eng J - Journal Article
Cullum, J. K. - Johnson, K. - Tůma, Miroslav
Effects of Problem Decomposition (Partitioning) on the Rate of Convergence of Parallel Numerical Algorithms.
[Vliv způsobu dekompozice problému na rychlost konvergence paralelních numerických algoritmů.]
Numerical Linear Algebra with Applications. Roč. 10, - (2003), s. 445-465. ISSN 1070-5325. E-ISSN 1099-1506
R&D Projects: GA ČR GA201/02/0595; GA AV ČR IAA1030103
Institutional research plan: CEZ:AV0Z1030915
Keywords : parallel algorithms * graph partitioning * problem decomposition * rate of convergence
Subject RIV: BA - General Mathematics
Impact factor: 1.042, year: 2003

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 ...

V tomto článku je hlavním obsahem vzájemná role dělení grafu, který vyjadřuje oblast modelu, ze které vznikl problém a rychlosti konvergence odpovídajících paralelních numerických algoritmů. Problémem je v tomto případě řešení rozsáhlé soustavy lineárních algebraických rovnic. Specifickým postupem ukazujeme jak toto dělení rychlost konvergence ovlivňuje. Závislost je vyjádřena volbou problému i algoritmem dělení. V článku dále ukazujeme jak zvýšit v některých případech robustnost dělení zavedením korekce Schurova doplňku. Naše numerické experimenty ukazují, že metoda dělení může poskytnout cenné informace pro zýšení robustnosti specifických implementací paralelních algoritmů.
Permanent Link: http://hdl.handle.net/11104/0152907