Skip to main content

LUP Student Papers

LUND UNIVERSITY LIBRARIES

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

Chrintz, Henrik LU (2022) In Bachelor's Theses in Mathematical Sciences NUMK01 20182
Mathematics (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:
author
Chrintz, Henrik LU
supervisor
organization
course
NUMK01 20182
year
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}},
}