Parallelization of stationary linear iterative methods for solving Poisson type PDE's

In this paper a parallel implementation of three methods, Jacobi, Gauss-Seidel and Successive over relaxation (SOR), for solving large and sparse linear systems derived from Poisson type PDEs are investigated in order to find the faster solver method. Workload which is decoupled can be done faster in parallel than sequentially. We use a grid to discretize the PDE and the order of the grid cells yields the order of the equations in the system, called the lexicographical- or natural order. The natural order of the equations in the linear systems introduces coupling when Gauss-Seidel and SOR are applied. This coupling can be reduced by using a different order, namely the Red-Black order. Another motivation to investigate the three methods is to use them as preconditioners to other iterative algorithms such as GMRES, CG and Multi-grid. By solving problems of varying sizes with varying number of parallel processes the performance can be measured and compared. Using more processes is faster for larger problems, but not as beneficial for small problems. For the problems considered in this work SOR is faster than Gauss-Seidel which is in turn faster than Jacobi.