Seyrek doğrusal sistemleri çözmek için satır blok bölümlemeye dayalı paralel direkt ve hibrit metotlar

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 system. Experimental results show that BCDcols significantly improves the convergence rate of block Cimmino method and hence reduces the parallel solution time.