Scheduling parallel iterative methods on multiprocessor systems (Q580891)

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.