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ı: 117
Ö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
- Effects of soil conditions on building damage distribution during 1 October 1995 Dinar eartquake: A reevaluation
Zemin koşullarının 1 Ekim 1995 Dinar depremi sırasında bina hasar dağılımına etkisi: Yeniden değerlendirme
SERAP KALIR
Yüksek Lisans
İngilizce
2000
İnşaat MühendisliğiOrta Doğu Teknik Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
PROF. DR. M. YENER ÖZKAN
- Reevaluating the historical spatial structure of the Ankara Atatürk boulevard as a sequence of urban spaces and plazas
Başlık çevirisi yok
ÖZLEM ELDEMİR(ORTABOY)
- Reevaluating a project of modernization: Design principles for the future of the Atatürk Rorest Farm
Bir modernleşme projesinin yeniden değerlendirilmesi: Atatürk Orman Çiftliği'nin geleceği için tasarım prensipleri
MURAT AYDINOĞLU
Yüksek Lisans
İngilizce
2018
MimarlıkOrta Doğu Teknik ÜniversitesiMimarlık Ana Bilim Dalı
PROF. DR. TOMRİS ELVAN ALTAN
PROF. DR. ALİ CENGİZKAN
- Mapping Hadîkatü'l-Cevâmi': Reevaluating an encyclopedia of Islamic monuments in the eighteenth century Ottoman Istanbul
Hadîkatü'l-Cevâmi'yi haritalamak: On sekizinci yüzyıl Osmanlı İstanbul'undaki İslam eserleri ansiklopedisinin yeniden değerlendirmesi
ABDULLAH SEÇGİN