Tez No	İndirme	Tez Künye	Durumu
470034		Parallel direct and hybrid methods based on row block partitioning for solving sparse linear systems / Seyrek doğrusal sistemleri çözmek için satır blok bölümlemeye dayalı paralel direkt ve hibrit metotlar Yazar:FAHREDDİN ŞÜKRÜ TORUN Danışman: PROF. DR. CEVDET AYKANAT ; DOÇ. DR. MURAT MANGUOĞLU Yer Bilgisi: İhsan Doğramacı Bilkent Üniversitesi / Mühendislik ve Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control Dizin:Dağıtık bilgisayar sistemi = Distributed computer system ; Grafik bölümleme = Graph partitioning ; Paralel bilgisayarlar = Parallel computers ; Seyrek matrisler = Sparse matrixes ; Çok işlemcili bilgisayarlar = Multiprocessor computers	Onaylandı Doktora İngilizce 2017 132 s.
Doğrusal sistemleri çözmek, bir çok bilimsel ve endüstriyel uygulamalarda çekirdek bir işlemdir. Bu uygulamalar genellikle büyük ve seyrek katsayı matrisi içeren doğrusal sistemler meydana getirmektedirler. Bu büyük ve seyrek matrisleri makul bir zamanda çözme ihtiyacı, etkin ve verimli paralel çözüm metodlarını gerekli kılmaktadır. Bu tezde, doğrusal sistemlerin paralel çözüm zamanlarını hızlandıran üç yeni ve orjinal yaklaşım sunulmaktadır. İlk olarak, katsayı matrisi sütun kesişen blok köşegen biçiminde olan eksik-tanımlı (underdetermined) doğrusal sistemlerin en küçük 2-norm çözümünü bulan yeni bir paralel algoritma olan ParBaMiN sunulmaktadır. Paylaşılan bellek (shared memory) ve dağıtık bellek (distributed memory) mimarilerinde yapılan deneyler ParBaMiN'in ölçeklenebilirliğini göstermektedir. İkinci olarak, blok Cimmino algoritmasının iterasyon sayısını düşürmek için yeni bir çizge-kuramsal bölümleme metodu önerilmektedir. Deney sonuçları, gerekli iterasyon sayısının azalımı bakımından önerilen metodun etkinliğini doğrulamaktadır. Son olarak, yoğun (dense) sütunlari olan matrisler için blok Cimmino algoritmasının iterasyon sayısını daha da azaltan yeni bir paralel hibrit metot olan BCDcols'u sunmaktayız. BCDcols, sistemin çözümü için blok Cimmino iteratif algoritması ile bir yoğun direkt çözüm metodunu birleştirmektedir. Deneysel sonuçlar, BCDcols'un blok Cimmino algoritmasının yakınsama hızını önemli ölçüde iyileştirdiğini göstermektedir ve böylelikle çözüme ulaşmak için gereken paralel zamanı azaltmaktadır.
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.