Parallelization of stationary linear iterative methods for solving Poisson type PDE's
(2022) In Bachelor's Theses in Mathematical Sciences NUMK01 20182Mathematics (Faculty of Engineering)
- Abstract
- 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... (More)
- 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. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/student-papers/record/9076059
- author
- Chrintz, Henrik LU
- supervisor
- organization
- course
- NUMK01 20182
- year
- 2022
- type
- M2 - Bachelor Degree
- subject
- keywords
- iterative method, SPD, SOR, Gauss-Seidel, Jacobi, discrete Laplacian, preconditioner, red-black ordering, parallel, MPI
- publication/series
- Bachelor's Theses in Mathematical Sciences
- report number
- LUNFNA-4052-2022
- ISSN
- 1654-6229
- other publication id
- 2022:K23
- language
- English
- id
- 9076059
- date added to LUP
- 2024-04-15 17:04:18
- date last changed
- 2024-04-15 17:04:18
@misc{9076059, abstract = {{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.}}, author = {{Chrintz, Henrik}}, issn = {{1654-6229}}, language = {{eng}}, note = {{Student Paper}}, series = {{Bachelor's Theses in Mathematical Sciences}}, title = {{Parallelization of stationary linear iterative methods for solving Poisson type PDE's}}, year = {{2022}}, }