Scheduling parallel iterative methods on multiprocessor systems. (English) Zbl 0626.65023

The paper describes the implementation of the successive overrelaxation (SOR) method on an asynchronous multiprocessor computer for solving large, linear systems. The parallel algorithm is derived by dividing the serial SOR method into noninterfering tasks which are then combined with an optimal schedule of a feasible number of processors. The important features of the algorithm are: (i) achieves a speedup \(S_ p\simeq O(N/3)\) and an efficiency \(E_ p\simeq 2/3\) using \(p=[N/2]\) processors, where N is the number of the equations, (ii) contains a high level of inherent parallelism, whereas on the other hand, the convergence theory of the parallel SOR method is the same as its sequential counterpart and (iii) may be modified to use block methods in order to minimize the overhead due to communication and synchronization of the processors.


65F10 Iterative numerical methods for linear systems
65F50 Computational methods for sparse matrices
65Y05 Parallel numerical computation
Full Text: DOI