Bilkent University
Department of Computer Engineering


Distributed-memory parallelization of Gauss Seidel Algorithm


Onur Koçak
MS Student
Computer Engineering Department
Bilkent University

In numerical algebra, Gauss-Seidel is a well-known iterative method of solving linear system of equations. The computations performed on Gauss-Seidel sweeps appear to be serial since each component of new iterations depends on previously computed results. The convergence is only guaranteed if the matrix is strictly diagonally dominant or positive definite and symmetric. There are several methods of extracting parallelism in Gauss-Seidel through performing special orderings on sparse matrices to eliminate data dependency caused by precedence in the calculations. In this study, we address load balancing and communication overhead issues of parallel Gauss-Seidel implementation and propose a computing model based on coarsening, graph coloring and hypergraph partitioning.


DATE: 26 March, 2018, Monday, CS590 & CS690 presentations begin at @ 15:40