Bilkent University
Department of Computer Engineering

---

MS THESIS PRESENTATION

 

Coloring for Distributed-Memory-Parallel Gauss-Seidel Algorithm

 

Onur Koçak
MS Student
(Supervisor: Prof. Dr. Cevdet Aykanat)
Computer Engineering Department
Bilkent University

Gauss-Seidel is a well-known iterative method for solving linear system of equations. The computations performed on Gauss-Seidel sweeps are sequential in nature since each component of new iterations depends on previously computed results. Graph coloring is widely used for extracting parallelism in Gauss-Seidel by eliminating data dependencies caused by precedence in the calculations. In this thesis, we present a method to provide a better coloring for distributed-memory-parallel Gauss-Seidel algorithm. Our method utilizes combinatorial approaches including graph partitioning and balanced graph coloring in order to decrease the number of colors while maintaining a computational load balance among the color classes. Experiments performed on irregular sparse problems arising from various scienti?c applications show that our model e?ectively reduces the required number of colors thus the number of Gauss Jacobi sweeps in the Gauss-Seidel algorithm.

 

DATE: 06 September 2019, Friday @ 11:00
PLACE: EA-409