Parallel Asynchronous Algorithms III. Application, Performances

In our first article [AF 1 385] , we presented the mathematical model describing asynchronous parallel iterative methods for solving univariate and multivariate pseudo-linear problems, the latter corresponding to the situation where the solution is subject to inequality constraints. We have also presented three separate methods for analyzing the behavior of these iterative methods, under suitable assumptions. The convergence of these methods can be analyzed either by contraction techniques, or by partial-order techniques linked to the use of the discrete maximum principle, or because successive iterates belong to nested sets centered on the solution U ^* of the problem to be solved. It should be noted that this last approach, based on nested sets, unifies the two previous approaches based on contraction or partial order techniques, but does not provide practical convergence criteria. A comparison of these three analysis techniques has revealed the advantages of each; in particular, under suitable assumptions, contraction techniques give an estimate of the asymptotic speed of convergence of these iterative methods, and obtain a convergence property whatever the block decomposition of the problem to be solved. What's more, this type of contraction analysis can be used to solve univocal and multivocal pseudo-linear problems, whereas partial-order techniques can only be used to solve univocal pseudo-linear problems, since the continuity assumption required in the analysis criterion for partial-order techniques is not satisfied.

Also in this first article [AF 1 385] , various methods for decomposing the problem to be solved into blocks were indicated. These include sub-domain methods and, more generally, multi-decomposition methods. Thanks to the results established above, the behavior of these methods has been analyzed. Finally, this article presents a number of examples of classical problems where the analysis criteria have been practically applied.

The following article