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
- Tez No: 470034
- Danışmanlar: PROF. DR. CEVDET AYKANAT, DOÇ. DR. MURAT MANGUOĞLU
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2017
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 132
Özet
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.
Özet (Çeviri)
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.
Benzer Tezler
- Fast direct volume rendering of unstructured grids
Düzensiz ızgaraların hızlı direk hacim görüntülenmesi
HAKAN BERK
Yüksek Lisans
İngilizce
1997
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiPROF. DR. BÜLENT ÖZGÜÇ
- Menzili uzatılmış elektrikli araçlarda eş değer yakıt tüketimi ile yakıt ve nox optimizasyonu
Nox and fuel optimization on range extended vehicles using equivalent consumption of minimization strategy
AYŞEGÜL KURŞUN
Yüksek Lisans
Türkçe
2014
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiKontrol ve Otomasyon Mühendisliği Ana Bilim Dalı
PROF. DR. SALMAN KURTULAN
- Elektrostatik alanların sonlu farklar yöntemiyle incelenmesi
Electrostatic field analysis by finite difference methods
SUPHİ YARICI
Yüksek Lisans
Türkçe
1992
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiPROF. DR. MUZAFFER ÖZKAYA
- Bulanık PID kontrolörleri için birleştirme operatörüne dayalı yeni bir öz-ayarlama yöntemi tasarımı
A novel self-tuning method based on aggregation operator for fuzzy PID controllers
ÇAĞRI GÜZAY
Yüksek Lisans
Türkçe
2014
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiKontrol ve Otomasyon Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. ENGİN YEŞİL
- On the analysis and evaluation of sparse hybrid linear solvers
Sparse hibrit doğrusal çözücülerinin analizi ve değerlendirilmesi
AFRAH NAJIB ABDULLAH FAREA
Yüksek Lisans
İngilizce
2018
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiHesaplamalı Bilimler ve Mühendislik Ana Bilim Dalı
PROF. DR. MUSTAFA SERDAR ÇELEBİ