Bilkent University
Department of Computer Engineering
Ph.D DISSERTATION
Parallel Direct and Hybrid Methods Based on Row Block Partitioning for Solving Sparse Linear Systems
Fahreddin Şükrü Torun
Ph.D Candidate
(Supervisor: Prof. Dr. Cevdet Aykanat)
(Co-supervisor: Assoc. Prof. Dr. Murat Manguoğlu)
Computer Engineering Department
Bilkent University
Solving system of linear equations is a kernel operation in many scientific and industrial applications. These applications usually give rise to linear systems in which the coefficient matrix is very large and sparse. The need for solving these large and sparse systems within a reasonable time necessitates efficient and effective parallel solution methods. In this thesis, three novel approaches are proposed for reducing the parallel solution time of linear systems. First, a new parallel algorithm, ParBaMiN, is proposed in order to find the minimum 2-norm solution of underdetermined linear systems, where the coefficient matrix is in the form of column overlapping block diagonal. The conducted experiments demonstrate the scalability of ParBaMiN on both shared and distributed memory architectures. Secondly, a new graph theoretical partitioning method is introduced in order to reduce the number of iterations in block Cimmino algorithm. Experimental results validate the effectiveness of the proposed partitioning method in terms of reducing the required number of iterations. Finally, we propose a new parallel hybrid method, BCDcols, which further reduces the number of iterations of block Cimmino algorithm for matrices with dense columns. BCDcols combines the block Cimmino iterative algorithm and a dense direct method for solving the linear system. Experimental results show that BCDcols significantly improves the convergence rate of block Cimmino algorithm and hence reduces the parallel solution time.
DATE: 16 August, 2017, Wednesday @ 13:00
PLACE: EA-409