Asynchronous Iterative Methods for Multiprocessors

A class of asynchronous lterative methods is presented for solving a system of equations Exlstmg lteratwe methods are identified in terms of asynchronous iterations, and new schemes are introduced corresponding to a parallel implementation on a multiprocessor system with no synchronization between cooperating processes A suffloent condlnon is given to guarantee the convergence of any asynchronous iterations, and results are extended to include lteratlve methods with memory Asynchronous lteratlve methods are then evaluated from a computational point of view, and bounds are dertved for the efficiency The bounds are compared with actual measurements obtained by running various asynchronous iterations on a mulnprocessor, and the experimental results show clearly the advantage of purely, as~,nchronous lterattve methods KEY WORDS AND PHRASES asynchronous algorithms, asynchronous muhiprocessors, parallel algorithms, lteratwe methods, chaotic relaxation, analysis of algorithms CR CATE6ORIES 5 14, 5.15, 5 25 contracting operators (see, for example, 9, p. 433)