Reevaluating spectral partitioning for unsymmetric matrices
Simetrik olmayan matrisler için spektral bölümlemeyi yeniden değerlendirme
- Tez No: 648872
- Danışmanlar: PROF. DR. MURAT MANGUOĞLU, DOÇ. DR. HAMDULLAH YÜCEL
- Tez Türü: Yüksek Lisans
- Konular: Matematik, Mathematics
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2020
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Uygulamalı Matematik Enstitüsü
- Ana Bilim Dalı: Bilimsel Hesaplama Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Grafik temsiline sahip bilimsel problemlerin paralel çözümleri, verimli görev ve veri bölümleme gerektirir. Bu tezde, çeşitli paralel grafik bölümleme algoritmaları incelenmiştir. Bu algoritmalar hem yönlendirilmiş hem de yönsüz grafiklere uygulanabilir olsa da, bu çalışmada, matris gösterimleri seyrek ve simetrik olmayan, hesaplamalı akışkanlar dinamiği ve termal problemler gibi çeşitli uygulama alanlarını temsil eden doğrusal denklem sisteminde ortaya çıkan yönlendirilmiş duruma odaklanıyoruz. Bu çalışmada incelenen stratejiler, Çok Seviyeli Kernighan-Lin algoritmasına sahip ParMETIS, k-ortalamalı kümeleme algoritması ile birlikte kullanılan spektral bölümleme (SPEC), ve CHACO içerisinde kullanılan spektral bölümleme algoritmasıdır. PETSc ve SLEPc kitaplıkları kullanılarak C programlama dilinde SPEC algoritması uygulanmış olup, CHACO ve ParMETIS ise PETSc'den çağrılmaktadır. Grafiğin kenar ağırlıkları dikkate alınarak ağırlıklı bölümlendirme yapılır. Ağırlıklı bölümleme yapıldığında kitaplıkların sınırlamaları nedeniyle SPEC, kitaplıklarla yalnızca ağırlıksız bölümleme yapıldığında karşılaştırılır. Bu nedenle, ağırlıklı bölümleme için, sadece SLEPc'deki çeşitli özdeğer çözücü toleransları, kenar kesme ve bölümleme süresi açısından incelenir. Başka bir araştırma ise MATLAB içerisinde k-ortalamalı kümeleme algoritması tarafından kullanıldığında, özdeğer çözücü toleransına dayalı spektral bölümleme algoritması için yapılmıştır. Karşılaştırma, bölümlemenin kalitesine (kenar kesimi ve bölüm dengesizliği) ve yineleme sayısı cinsinden maliyete dayanmaktadır. Bir bölümlemenin kalitesi, uygulamaya bağlı olarak bölümlerin kenar ve tepe dengesizlik oranlarına bağlı olabilecek yük dengesizliğinin yanı sıra kesilen kenar sayısı ile belirlenir. Bir grafiğin bitişik matrisi yapısal olarak simetrik olduğundan, matris simetrik olmadığında özdeğer problemi ancak yaklaşık olarak çözülebilir. Bu nedenle, bu çalışmada yalnızca yaklaşık sonuçlar verilmiştir. Simetrik olmayan matrislerin ağırlıksız bölümlemesinde kenar kesim sayısı karşılaştırıldığında, SPEC kullanımının mevcut yazılım kitaplıklarından daha iyi performans gösterdiği sonucuna varılmıştır.
Özet (Çeviri)
Parallel solutions to scientific problems having graph representation require efficient tasks and partitioning data. In this thesis, various parallel graph partitioning algorithms are studied. While these algorithms are applicable to both directed and undirected graphs, we focus on the directed case whose matrix representations are sparse and unsymmetric arising in linear system of equations representing various application domains such as computational fluid dynamics and thermal problems. Strategies inspected in this study are ParMETIS with the Multilevel Kernighan-Lin algorithm and the spectral partitioning algorithm with k-means clustering (SPEC) as well as the recursive spectral partitioning algorithm in CHACO. We have implemented SPEC in C programming language using PETSc and SLEPc libraries, whereas CHACO and ParMETIS are called from PETSc. Weighted partitioning is done under the consideration of the edge weights of the graph. SPEC is compared with the libraries only when the unweighted partitioning is made due to the limitations of the libraries for weighted partitioning. Hence, for weighted partitioning, only various eigensolver tolerances in SLEPc are studied in terms of the edge-cut and partitioning time. Another study is performed for the spectral partitioning algorithm based on eigensolver tolerance used with the k-means algorithm in MATLAB. The comparison is based on the quality of the partitioning (edge-cut and partition imbalance) and the number of iterations. The quality of partitioning is determined by the edge-cut and the load imbalance, which could be based on the edge and vertex imbalance ratios of partitions depending on the application. Since the adjacency matrix of a graph is structurally symmetric, the eigenvalue problem can only be solved approximately when the matrix is unsymmetric. Thus, only approximate results are provided in this study. It is deduced that using SPEC performs better than the existing software libraries when the number of cut edges is compared in unweighted partitioning of unsymmetric matrices.
Benzer Tezler
- Simetrik konsollu köprü ayaklarının temel ivmeleri altında dinamik ve spektral analizi
Başlık çevirisi yok
HAVVA ÜLKÜ ŞENEL
Yüksek Lisans
Türkçe
1998
İnşaat Mühendisliğiİstanbul Teknik Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
PROF. DR. ZEKİ HASGÜR
- Düzlemsel dalgaların farklı sınır koşullarına sahip paralel iki yarım düzlemden kırınımı
Plane wave diffraction by a pour of soft and hard complementary half planes
ERDEM TOPSAKAL
Yüksek Lisans
Türkçe
1993
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiPROF.DR. MİTHAT İDEMEN
- Acil servise senkop ile başvuran hastaların değerlendirilmesinde karotis doppler ultrasongrafi'nin etkinliğinin değerlendirilmesi
In the evaluation of patients presenting with syncope to the emergency department evaluation of the efficacy of carotid doppler ultrasonography
KÜBRA SELÇOK
Tıpta Uzmanlık
Türkçe
2019
İlk ve Acil YardımSağlık Bilimleri ÜniversitesiAcil Tıp Ana Bilim Dalı
DR. ÖĞR. ÜYESİ HÜSEYİN CAHİT HALHALLI
- Subjektif tinnituslu bireylerde zamansal ve eşiküstü işitsel işlemlemenin değerlendirilmesi
Evaluation of temporal and suprathreshold auditory processing in individuals with subjective tinnitus
KÜRŞAD KARAKOÇ
Doktora
Türkçe
2024
Kulak Burun ve BoğazAnkara ÜniversitesiKulak Burun Boğaz Hastalıkları Ana Bilim Dalı
PROF. DR. CEM MEÇO
- Kesme pimi tasarımında çentik geometrisi parametrelerinin pim dayanımına etkisinin incelenmesi
Examining the impact of groove profiles and dimensional parameters on shear pin strength
MEHMET OZAN YİTİM
Yüksek Lisans
Türkçe
2025
Makine Mühendisliğiİstanbul Teknik ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
PROF. DR. CEVAT ERDEM İMRAK