Parallel asynchronous algorithms: A survey. (November 2020) - Spiteri, Pierre
Highlights: Parallel asynchronous iterative methods and their extensions are presented and analyzed. Behavior of algorithms is analyzed by contraction property, partial ordering property and nestedsets. Stopping tests of iterations are presented derived both from computer science and from numerical analysis approach. Principle of implementation of these methods is described for subdomain methods with and without overlapping. Various applications related to pseudo - linear systems eventually constrained of such algorithms are presented. Abstract: This paper deals with a synthetic presentation of parallel iterative asynchronous algorithms and their extensions for the solution of large sparse linear or pseudo-linear algebraic systems eventually constrained. The behavior of these iterative parallel asynchronous algorithms is studied by three distinct methods : contraction property, partial ordering property linked to the discrete maximum principle and nested sets; the link between these three kinds of analysis is presented. Stopping tests of the iterations are presented both from computer science and from numerical analysis approach including in this last case approximate contraction property, partial ordering property linked to the discrete maximum principle and nested sets. The principle of implementation of these parallel asynchronous iterative methods is described for subdomain method without overlapping and for subdomain method with overlapping; the use of load balancing approach for asynchronous parallel algorithms is also discussed. Various applications modelled by linear equations or pseudo linear equations and solved by such parallel algorithms are presented as well as the uses of these methods in computer security and Boolean calculation. The efficiency of parallel iterative asynchronous algorithms is also discussed.