Parallelization of 'Gauss-Seidel' Algorithms as an Example of Parallel Iterative Equation Solving

摘要

In chapter 1, the parallelization of the point Gauss-Seidel (G.S.) algorithm is studied for nonlinear equations in the case that the equation solving is done by sequential subtask processing. Data flow analysis shows that m equations can be processed by p=m processors in parallel by means of so-called skewed parallel batch processing with an asymptotic causal speed-up s(sub c, infinity)=p and ditto causal efficiency e(sub c, infinity)=1. In chapter 2, the parallelization of the point G.S. algorithm is studied for linear equations. First, in the case of sequential equation solving, the authors discuss how to apply skewed parallel processing for full matrices as well as for band matrices. Section 2.4 discusses some parallel point G.S. algorithms obtained by parallelization of the function evaluations by means of parallel-sequential algorithms. G.S. algorithms can not be more than m as a consequence of the fact that point iterative methods have a low degree of explicity. In chapter 3, the parallelization of the multi-point and block G.S. algorithms is studied (for linear equations) in order to demonstrate that an increase of explicity results in more speed-up.